记录编号	614066	评测结果	AAAATTTTTT
题目名称	4371.大括号	最终得分	40
用户昵称	RpUtl	是否通过	未通过
代码语言	C++	运行时间	6.672 s
提交时间	2026-04-04 11:44:05	内存使用	6.67 MiB

#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;
}