oj.uz

Submission #72045

# Submission time Handle Problem Language Result Execution time Memory
72045 2018-08-26T04:56:01 Z 고독한 참가자(#2174, kriii) Dstorv (FXCUP3_dstorv) C++17
0 / 100
 326 ms 47424 KB 
#include <stdio.h>

int N,A,B,r,h; char S[5050];
int prs[5050],phs[5050]; long long pc[5050];
int srs[5050],shs[5050]; long long sc[5050];
const long long mod = 1000000007;
long long inv[2002002]={0,1},fact[2002002]={1,1},ifact[2002002]={1,1};

long long fpow(long long a, long long p)
{
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

long long comb(int n, int k)
{
	if (n < 0 || k < 0 || k > n) return 0;
	return fact[n] * ifact[k] % mod * ifact[n-k] % mod;
}

int main()
{
	for (int i=2;i<2002002;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}

	scanf ("%d %d %d",&N,&A,&B);
	scanf ("%s",S+1);
	scanf ("%d %d",&r,&h);

	for (int i=1;i<=N;i++){
		prs[i] = prs[i-1] + (S[i] == 'R');
		phs[i] = phs[i-1] + (S[i] == 'H');
		pc[i] = pc[i-1] + (S[i] == 'H') * prs[i];
	}
	for (int i=N;i>=1;i--){
		srs[i] = srs[i+1] + (S[i] == 'R');
		shs[i] = shs[i+1] + (S[i] == 'H');
		sc[i] = sc[i+1] + (S[i] == 'R') * shs[i];
	}
	S[0] = 'H'; S[N+1] = 'R';

	long long rw = r * inv[r+h] % mod;
	long long hw = h * inv[r+h] % mod;

	long long ans = 0;
	for (int i=1;i<=N+1;i++) if (S[i-1] == 'H' && S[i] == 'R'){
		long long p = 0;
		long long q = 0;
		if (phs[i-1] >= B){
			int d = phs[i-1] - B;
			if (pc[i-1] >= d)
				p = fpow(rw,d) * fpow(hw,pc[i-1]-d) % mod * comb(pc[i-1],d) % mod;
		}
		if (srs[i] >= A){
			int d = srs[i]-A;
			if (sc[i] >= d)
				q = fpow(hw,d) * fpow(rw,sc[i]-d) % mod * comb(sc[i],d) % mod;
		}
		ans = (ans + p * q) % mod;
	}

	printf ("%lld\n",ans);

	return 0;
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d",&N,&A,&B);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%s",S+1);
  ~~~~~~^~~~~~~~~~
dstorv.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&r,&h);
  ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 62.0

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