AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)
問題文
省略
省略
C++に変換後のコードはこちら
#define MD 998244353
int N;
char S[1d6+2];
int bt[1d6+2], bl[23], br[23], bef[1d6+1];
Modint dp[23][1d6+1], dps[23][1d6+1];
{
int i, j, k, nk, x, y;
Modint res;
rd(S@N);
rep(i,2,1d6+2) bt[i] = bt[(i+1)/2] + 1;
rep(i,23) bl[i] = int_inf, br[i] = -int_inf;
rep(i,1d6+2) bl[bt[i]] <?= i, br[bt[i]] >?= i;
rep(i,1,N){
bef[i] = bef[i-1];
if(S[i-1] == 'B') bef[i] = i-1;
}
rep(i,N){
if(S[i] == 'B' || S[i] == '?') dp[22][i] = 1;
if(S[i] == 'B') break;
}
rep(i,N){
if(S[i] == 'B' || S[i] == '?'){
rep(j,1,23) rep(k,1,23){
x = max(bef[i], i - br[j]);
y = i - bl[j];
if(x > y) continue;
nk = min(j, k-1);
dp[nk][i] += dps[k][y+1] - dps[k][x];
}
}
rep(k,1,23) dps[k][i+1] = dps[k][i] + dp[k][i];
}
res = 1;
rep(i,N) if(S[i] == '?') res *= 2;
rrep(i,N){
rep(j,1,23) res -= dp[j][i];
if(S[i]=='B') break;
}
rep(i,N) if(S[i] == 'B') break;
if(i==N) res -= 1;
wt(res);
}
Current time: 2024年03月29日14時25分38秒
Last modified: 2020年12月28日21時11分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC050 AGC_C
トップページに戻る
Logged in as: unknown user (not login)