P7969 [KSN2021] Self Defence

我的算法是”云 力“ ”太 心“ 规划啥玩意设]为填了前i个字符此时字符串权值为j第i个字符是A/B的方案数。设表示第i位前第一个已经填好的A/B。当的时候。当的时候然后最后答案为。时间复杂度为。考虑前缀和优化。对于有贡献的部分我们发现所以可以令表示所有的于是时间复杂度就变成了了。代码求赞#includebits/stdc.h using namespace std; const int N3e310,mod1e97; int n,m,k,x0,y0,pre[N][2],dp[N][N][2],s1[N][N][2],s2[N][N*2][2]; //设dp[i][j][0/1]为填了前i个字符此时字符串权值为j第i个字符是A/B的方案数。 //设pre[i][0/1]表示第i位前第一个已经填好的A/B。 string s; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnmk; cins; s_s; for(int i1;in;i){ if(s[i]A) xi; else if(s[i]B) yi; pre[i][0]x,pre[i][1]y; } dp[0][0][0]dp[0][0][1]1; s1[0][0][0]s1[0][0][1]1; s2[0][n][0]s2[0][n][1]1; for(int i1;in;i){ for(int j0;jk;j){ if(s[i]?){ for(int x0;x1;x){ if(i-pre[i][1-x]m){ dp[i][j][x]((s1[i-1][j][1-x]-(pre[i][1-x] ? s1[pre[i][1-x]-1][j][1-x] : 0)%modmod)%mod); }else{ dp[i][j][x]((s1[i-1][j][1-x]-s1[i-m][j][1-x])%modmod)%mod; dp[i][j][x](((dp[i][j][x]s2[i-m][j-im-1n][1-x])%mod-(pre[i][1-x] ? s2[pre[i][1-x]-1][j-im-1n][1-x] : 0))%modmod)%mod; } } }else{ xs[i]-A; if(i-pre[i][1-x]m){ dp[i][j][x]((s1[i-1][j][1-x]-(pre[i][1-x] ? s1[pre[i][1-x]-1][j][1-x] : 0)%modmod)%mod); }else{ dp[i][j][x]((s1[i-1][j][1-x]-s1[i-m][j][1-x])%modmod)%mod; dp[i][j][x](((dp[i][j][x]s2[i-m][j-im-1n][1-x])%mod-(pre[i][1-x] ? s2[pre[i][1-x]-1][j-im-1n][1-x] : 0))%modmod)%mod; } } s1[i][j][0](s1[i-1][j][0]dp[i][j][0])%mod; s1[i][j][1](s1[i-1][j][1]dp[i][j][1])%mod; s2[i][j-in][0](s2[i-1][j-in][0]dp[i][j][0])%mod; s2[i][j-in][1](s2[i-1][j-in][1]dp[i][j][1])%mod; } } bool flag0; for(int i0;is.size();i){ if(s[i]!?){ flag1; break; } } cout(dp[n][k][0]dp[n][k][1])%mod; return ~(-1); }