Submission #72045

#	Time	Username	Problem	Language	Result	Execution time	Memory
72045		고독한 참가자 (#118)	Dstorv (FXCUP3_dstorv)	C++17	0 / 100	326 ms	47424 KiB

dstorv

#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 (stderr)

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
• Subtask 2: 0 / 29
• Subtask 3: 0 / 62