Submission #1211219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211219		yangbaich	Dstorv (FXCUP3_dstorv)	C++20	0 / 100	1 ms	1096 KiB

dstorv

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5005;
int jc[N], inv;
int n, r, h, a, b, ps[N], m, dp[2][N][N], qzh[2][N][N], inp[N], qza[N];
char s[N];
inline int Pow(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1)
			ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return ret;
}
int fpw[2][N], pw[2][N];
int main() {
	scanf("%d%d%d%s%d%d", &n, &r, &h, s + 1, &b,&a); 
	int inv=Pow(r+h,mod-2);
	pw[0][0] = pw[1][0] = fpw[0][0] = fpw[1][0] = 1;
	for (int i = 1;i <= n;i++) {
		pw[0][i] = 1ll * pw[0][i - 1] * h % mod * inv% mod;
		pw[1][i] = 1ll * pw[1][i - 1] * r % mod * inv% mod;
		fpw[0][i] = Pow(pw[0][i], mod - 2);
		fpw[1][i] = Pow(pw[1][i], mod - 2);
	}
	for (int i = n;i >= 1;i--)
		if (s[i] == 'R') {
			ps[++m] = i;
			inp[m] = i;
		}
	for (int i = 1;i <= n+1;i++)
		qza[i] = qza[i-1] + (s[i] == 'H');
	ps[0] = n + 1;
	for (int i = 0;i <= N - 5;i++)
		qzh[0][0][i] = 1;
	//	cout<<pw[1][1]<<"\n";
	for (int i = 1;i <= m;i++) {
		int B = i & 1;
		int hz = n - m - qza[ps[i]];
	//	cout<<"HZ"<<hz<<"\n";
		for (int j = 0;j <= i;j++)
			for (int k = 0;k <=hz;k++) {
				int ai = qza[ps[i - 1]] - qza[ps[i]];
			//	if(k!=hz){
		//	assert(hz + k - ai-1<=n - m - qza[ps[i-1]]);
					dp[B][j][k] = 1ll * pw[1][1] * (k - ai < 0 ? pw[0][ai - k] : fpw[0][k - ai]) % mod * ((hz + k - ai-1>=0?qzh[B ^ 1][j][min(n - m - qza[ps[i-1]],hz + k - ai-1)]:0) - (k - ai <= 0 ? 0 : qzh[B ^ 1][j][k - ai - 1])+mod) % mod;
		//			cout << i << " " << j << " " << k << " ai="<<ai<<" " << 1ll * pw[1][1] * (k - ai < 0 ? pw[0][ai - k] : fpw[0][k - ai]) % mod  << "\n";
		//			cout << hz + k - ai -1<< " " << k - ai - 1 << " "<<qzh[B ^ 1][j][hz + k - ai-1] <<"->"<< (qzh[B ^ 1][j][hz + k - ai] - (k - ai <= 0 ? 0 : qzh[B ^ 1][j][k - ai - 1])+mod) <<"\n"; 
			//	}
				if (!k && j)
					dp[B][j][k] = (dp[B][j][k] + 1ll*pw[0][ai]*qzh[B ^ 1][j - 1][n - m - qza[ps[i-1]]]%mod) % mod;
				qzh[B][j][k] = ((k?qzh[B][j][k - 1]:0) + 1ll * dp[i & 1][j][k] * pw[0][k] % mod) % mod;
		//		cout<<i<<" "<<j<<" "<<k<<"="<<dp[B][j][k]<<"\n\n";
			}
	}
//	cout<<(m&1)<<" "<<b<<" "<<a-qza[ps[m]]<<"\n";
	if (a < qza[ps[m]])
		cout << 0;
	else
		cout << dp[m & 1][b][a - qza[ps[m]]];
}

Compilation message (stderr)

dstorv.cpp: In function 'int main()':
dstorv.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d%d%d%s%d%d", &n, &r, &h, s + 1, &b,&a);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 29
• Subtask 3: 0 / 62