| 比赛 |
2026.4.4 |
评测结果 |
AAAATTTTTT |
| 题目名称 |
大括号 |
最终得分 |
40 |
| 用户昵称 |
终焉折枝 |
运行时间 |
6.668 s |
| 代码语言 |
C++ |
内存使用 |
6.73 MiB |
| 提交时间 |
2026-04-04 11:40:03 |
显示代码纯文本
#include<iostream>
using namespace std;
#define ciallo(x) cerr << x << '\n';
#define ll long long
const int MOD = 666623333;
const int MAXN = 5005;
ll qpow(ll a, ll b){
ll res = 1;
a %= MOD;
while(b){
if(b & 1) (res = res * a) %= MOD;
(a = a * a) %= MOD;
b >>= 1;
}
return res;
}
ll inv(int n){
return qpow(n, MOD - 2);
}
ll n, p, q, a, b;
ll dp[MAXN][MAXN];
string s;
ll Pow[MAXN];
int main(){
freopen("brace.in", "r", stdin);
freopen("brace.out", "w", stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
cin >> n >> p >> q;
cin >> a >> b;
cin >> s;
ll P = p * inv(p + q) % MOD;
ll Q = q * inv(p + q) % MOD;
Pow[0] = 1;
for(int i = 1;i <= n;i ++){
Pow[i] = (Pow[i - 1] * P) % MOD;
}
dp[0][0] = 1;
ll cl = 0, cr = 0;
for(int i = 0;i < s.size();i ++){
// ciallo(cl);
// ciallo(cr);
if(s[i] == 'R'){
cr ++;
for(int k = 0;k <= min(cl, a);k ++){
for(int j = cr;j >= 1;j --){
dp[k][j] = dp[k][j - 1];
}
dp[k][0] = 0;
}
}
else{
cl ++;
for(int k = min(cl, a);k >= 0;k --){
ll sur = 0;
for(int j = 0;j <= cr;j ++){
sur = (sur + (dp[k][j] * Pow[j]) % MOD) % MOD;
}
ll suf = 0;
for(int j = cr;j >= 1;j --){
suf = ((dp[k][j] * Q) % MOD + (suf * P) % MOD) % MOD;
dp[k][j] = suf;
}
dp[k][0] = 0;
if(k + 1 <= a) dp[k + 1][0] = (dp[k + 1][0] + sur) % MOD;
// ciallo(sur);
// ciallo(suf);
}
}
}
cout << dp[a][b] % MOD << '\n';
return 0;
}