oj.uz

Submission #72530

# Submission time Handle Problem Language Result Execution time Memory
72530 2018-08-26T08:49:51 Z RR rangers(#2172, jwvg0425, ozt88, choy907) Dstorv (FXCUP3_dstorv) C++17
0 / 100
 6 ms 976 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <sstream>
#include <iterator>
#define MOD ((i64)(1e9+7))

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

// table[r][h] = R이 r개, H가 h개 있을 때 둘다 0개가 될 확률
ii64 table[5001][5001];
ii64 flowerp, handp;
i64 facto[5001];

int a, b;

int n, r, h;
string s;

i64 ipow(i64 x, i64 k)
{
	if (k == 0)
		return 1;

	i64 half = ipow(x, k / 2);

	half = (half * half) % MOD;

	if (k % 2 == 0)
		return half;
	else
		return (half * x) % MOD;
}

ii64 calcLeft(int i)
{
	if (i == -1)
	{
		if (b == 0)
			return ii64(1, 1);

		return ii64(0, 1);
	}

	if (s[i] != 'H')
		return ii64(0, 1);

	int leftmost = -1;
	for (int j = 0; j <= i; j++)
	{
		if (s[j] == 'R')
		{
			leftmost = j;
			break;
		}
	}

	ii64 leftp = ii64(1, 1);
	int hl = 0, hr = 0;
	int remainr = 0;

	for (int j = 0; j <= i; j++)
	{
		if (s[j] != 'H')
		{
			remainr++;
			continue;
		}

		if (j <= leftmost)
			hl++;
		else
			hr++;
	}

	if (leftmost == -1)
	{
		if (hr != b)
			return ii64(0, 1);
	}
	else
	{
		int remain = b - hl;

		if (remain < 0)
			return ii64(0, 1);

		int need = hr - remain;

		if (need == hr || need < 0)
			return ii64(0, 1);

		//hr개 중에 remain개를 선택
		//C(hr,remain) = hr!/(hr-remain)! *remain!
		leftp = table[remainr][need];
		leftp.first = (leftp.first * facto[hr - 1]) % MOD;
		leftp.second = (leftp.second * facto[hr - remain]) % MOD;
		leftp.second = (leftp.second * facto[remain - 1]) % MOD;
	}

	return leftp;
}

ii64 calcRight(int i)
{
	if (i == s.size())
	{
		if (a == 0)
			return ii64(1, 1);

		return ii64(0, 1);
	}

	if (s[i] != 'R')
		return ii64(0, 1);

	ii64 rightp(1, 1);

	int rightmost = -1;
	for (int j = n - 1; j >= i; j--)
	{
		if (s[j] == 'H')
		{
			rightmost = j;
			break;
		}
	}

	int rl = 0, rr = 0;
	int remainh = 0;

	for (int j = n - 1; j >= i; j--)
	{
		if (s[j] != 'R')
		{
			remainh++;
			continue;
		}

		if (j >= rightmost)
			rr++;
		else
			rl++;
	}

	if (rightmost == -1)
	{
		if (rr != a)
			return ii64(0, 1);
	}
	else
	{
		int remain = a - rr;

		if (remain < 0)
			return ii64(0, 1);

		int need = rl - remain;

		if (need == rl || need < 0)
			return ii64(0, 1);

		rightp = table[need][remainh];
		rightp.first = (rightp.first * facto[rl - 1]) % MOD;
		rightp.second = (rightp.second * facto[rl - remain]) % MOD;
		rightp.second = (rightp.second * facto[remain - 1]) % MOD;
	}

	return rightp;
}

int main()
{
	scanf("%d %d %d", &n, &r, &h);

	cin >> s;

	table[0][0].first = table[0][0].second = 1;

	flowerp.first = h;
	flowerp.second = r + h;

	handp.first = r;
	handp.second = r + h;

	facto[0] = 1;

	for (int i = 1; i <= n; i++)
		facto[i] = (facto[i - 1] * i) % MOD;

	for(int flower = 0; flower <= n; flower ++)
	{
		for(int hand = 0; hand <= n; hand++)
		{
			if (flower == 0 && hand == 0)
				continue;

			table[flower][hand].first = ipow(handp.first, flower);
			table[flower][hand].second = ipow(handp.second, flower);

			table[flower][hand].first *= ipow(flowerp.first, hand);
			table[flower][hand].second *= ipow(flowerp.second, hand);

			table[flower][hand].first %= MOD;
			table[flower][hand].second %= MOD;
		}
	}

	scanf("%d %d", &a, &b);

	ii64 ans(0, 1);
	for (int i = 0; i <= s.size(); i++)
	{
		auto leftp = calcLeft(i - 1);
		auto rightp = calcRight(i);

		ii64 p(leftp.first * rightp.first % MOD, leftp.second * rightp.second % MOD);

		ans.first = ((ans.first * p.second) %MOD + (ans.second * p.first) % MOD) % MOD;
		ans.second = (ans.second * p.second) % MOD;
	}

	printf("%lld\n", (ans.first * ipow(ans.second, MOD - 2) % MOD));

	return 0;
}

Compilation message

dstorv.cpp: In function 'ii64 calcRight(int)':
dstorv.cpp:123:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i == s.size())
      ~~^~~~~~~~~~~
dstorv.cpp: In function 'int main()':
dstorv.cpp:229:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= s.size(); i++)
                  ~~^~~~~~~~~~~
dstorv.cpp:191:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:226:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Incorrect 2 ms 484 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Incorrect 2 ms 484 KB Output isn't correct
6 Halted 0 ms 0 KB -