很没感觉的一道题。
首先特判掉 \(n\le 2\)。
在 \(s\) 无穷拼接的过程中,我们考虑一个周期一个周期地匹配,由于每局比赛的长度是 \(2\) 或者 \(3\),因此每个周期开始的时候,把上个周期剩下的零头匹配完之后起始匹配位置只可能是 \(0\) 或 \(1\) 或 \(2\),并且对于一个起始匹配位置 \(i(0\le i\le 2)\),从这个位置开始匹配一轮以后到下个周期,存在唯一后继 \(to_i\)。而计算题目中那个极限是否 \(\ge 0\),就等价于将 \(i\to to_i\) 连边以后,\(0\) 所在连通块的环内的部分是 Alice 赢的多还是 Bob 赢的多。
我们枚举有效部分的起始位置集合(共 \(2^3\) 种),再枚举前三位的值(共 \(2^3\) 种),然后考虑 DP:\(dp_{i,j,a,b,c}\) 表示目前考虑到前 \(i\) 位,有效部分中 Alice 胜场次数减去 Bob 胜场次数 \(=j\),起始位置为 \(0,1,2\) 的匹配方案目前状态分别为 \(a,b,c\)(\(0:0,1:0,0:1,1:1\) 共四种)的方案数,这样最后统计答案的时候可以通过 \(a,b,c\) 算出 \(to_i\),进而检查起始位置集合是否真的是我们枚举的 mask,如果是就把 DP 值计入答案的贡献即可。
时间复杂度 \(O(n^2·4096)\),但是常数很小所以过了。
const int MAXN=200;
const int DLT=605;
const int MOD=998244353;
void add(int &x,int v){(x+=v)>=MOD&&(x-=MOD);}
int n;char s[MAXN+5];
int dp[MAXN+5][MAXN*6+10][4][4][4];
void trans0(int &j,int &A,int &B,int &C,int msk_in){
if(A==1||A==3){A=0;if(msk_in&1)--j;}else A|=1;
if(B==1||B==3){B=0;if(msk_in>>1&1)--j;}else B|=1;
if(C==1||C==3){C=0;if(msk_in>>2&1)--j;}else C|=1;
}
void trans1(int &j,int &A,int &B,int &C,int msk_in){
if(A==2||A==3){A=0;if(msk_in&1)++j;}else A|=2;
if(B==2||B==3){B=0;if(msk_in>>1&1)++j;}else B|=2;
if(C==2||C==3){C=0;if(msk_in>>2&1)++j;}else C|=2;
}
int main(){
scanf("%s",s+1);n=strlen(s+1);
if(n==1){
int A=0,B=0,C=0;
if(s[1]!='a')B++;
if(s[1]!='b')A++;
printf("%d\n%d\n%d\n",A,C,B);
return 0;
}if(n==2){
int A=0,B=0,C=0;
if(s[1]!='a'&&s[2]!='a')B++;
if(s[1]!='b'&&s[2]!='b')A++;
if(s[1]!='a'&&s[2]!='b')C++;
if(s[1]!='b'&&s[2]!='a')C++;
printf("%d\n%d\n%d\n",A,C,B);
return 0;
}
int res1=0,res2=0,res3=0;
for(int msk_in=1;msk_in<8;msk_in++){
int cnt=__builtin_popcount(msk_in);
for(int fst3=0;fst3<8;fst3++){
bool flg=1;
for(int i=1;i<=3;i++){
if(s[i]=='b'&&(fst3>>(i-1)&1))flg=0;
if(s[i]=='a'&&!(fst3>>(i-1)&1))flg=0;
}
if(!flg)continue;memset(dp,0,sizeof(dp));
int ini_j=0,ini_A=0,ini_B=0,ini_C=0,cmask=0;
for(int i=0;i<3;i++){
cmask|=(1<<i);cmask&=msk_in;
if(fst3>>i&1)trans1(ini_j,ini_A,ini_B,ini_C,cmask);
else trans0(ini_j,ini_A,ini_B,ini_C,cmask);
if(!i)ini_B=ini_C=0;else if(i==1)ini_C=0;
}
// if(fst3==6&&msk_in==2){
// printf("!! %d %d %d %d\n",ini_j,ini_A,ini_B,ini_C);
// }
dp[3][ini_j+DLT][ini_A][ini_B][ini_C]=1;
for(int i=4;i<=n;i++)for(int j=-i*cnt;j<=i*cnt;j++)
for(int A=0;A<4;A++)for(int B=0;B<4;B++)for(int C=0;C<4;C++){
if(dp[i-1][j+DLT][A][B][C]){
if(s[i]!='b'){
int tj=j,tA=A,tB=B,tC=C;
trans1(tj,tA,tB,tC,msk_in);
add(dp[i][tj+DLT][tA][tB][tC],dp[i-1][j+DLT][A][B][C]);
}
if(s[i]!='a'){
int tj=j,tA=A,tB=B,tC=C;
trans0(tj,tA,tB,tC,msk_in);
add(dp[i][tj+DLT][tA][tB][tC],dp[i-1][j+DLT][A][B][C]);
}
}
}
for(int A=0;A<4;A++)for(int B=0;B<4;B++)for(int C=0;C<4;C++){
for(int j=-cnt*n;j<=cnt*n;j++)if(dp[n][j+DLT][A][B][C]){
int tj=j,tA=A,tB=B,tC=C;
static int to[3];memset(to,-1,sizeof(to));
int tmp_msk_in=msk_in;
if(tA==0)to[0]=0,tmp_msk_in&=6;
if(tB==0)to[1]=0,tmp_msk_in&=5;
if(tC==0)to[2]=0,tmp_msk_in&=3;
for(int k=0;k<2;k++){
if(fst3>>k&1)trans1(tj,tA,tB,tC,tmp_msk_in);
else trans0(tj,tA,tB,tC,tmp_msk_in);
if(tA==0&&!~to[0])to[0]=k+1,tmp_msk_in&=6;
if(tB==0&&!~to[1])to[1]=k+1,tmp_msk_in&=5;
if(tC==0&&!~to[2])to[2]=k+1,tmp_msk_in&=3;
}
static bool vis[3];memset(vis,0,sizeof(vis));
int cur=0,msk=0;while(!vis[cur])vis[cur]=1,cur=to[cur];
for(int _=0;_<3;_++)msk|=(1<<cur),cur=to[cur];
if(msk==msk_in){
// printf("! %d %d %d %d %d %d way=%d %d\n",msk_in,fst3,j,A,B,C,dp[n][j+DLT][A][B][C],tj);
if(tj>0)add(res1,dp[n][j+DLT][A][B][C]);
else if(tj==0)add(res2,dp[n][j+DLT][A][B][C]);
else add(res3,dp[n][j+DLT][A][B][C]);
}
}
}
}
}
printf("%d\n%d\n%d\n",res1,res2,res3);
return 0;
}