.gif)
Codeforces 1785 E Infinite Game 題解 (圖論，自動機，dp)
假設現在字符串s中已經沒有問號，我們來確定這時的答案。我們建立一個4個點的有向圖(可以看成一個自動機)，4個點分別代表每個set內部的比分：0:0, 1:0, 0:1, 1:1。在其中連一些邊，比如從1:0往1:1連一條權值為0的邊，代表放一個字符b時會走這條邊，且對Alice贏的set數貢獻為0；從1:0往0:0連一條權值為1的邊，代表放一個字符a時會走這條邊，且對Alice贏的set數的貢獻為1。一共連8條這樣的邊，每個點的出度為2。然后令初始位置為0:0，我們從左到右遍歷s，當加入一個字符時就在圖中走對應的邊，把邊權加入答案，并把當前位置沿著這條邊移動一次。令\(to_i\)表示以狀態i為初始位置，遍歷完整個s后得到的狀態；\(val_i\)表示以狀態i為初始位置，遍歷完s的過程中給答案加上的值的和，其中\(i\in \{0:0,1:0,0:1,1:1 \}\)。我們把\(i\to to_i\)連邊，建出一個新圖。新圖的形態是一個內向基環樹，由于這題要求我們不斷重復s，也就相當于在新圖上從0:0開始不斷地走，并把經過的每個點的\(val_i\)加入答案。在這個新圖中，從0:0出發一定會到達基環，并在基環上不斷繞圈。令sum表示基環上所有點的\(val_i\)之和，如果\(sum>0\)，顯然當走的步數趨于無窮時Alice贏的set數更多；如果\(sum<0\)，顯然Bob贏的set數更多；否則\(sum=0\)，此時無論你在到達基環之前經過的點的\(val_i\)之和是正是負，當走的步數趨于無窮時，Alice與Bob贏的set數之差都是趨于0的，所以此時是平局。
然后來看原問題，考慮dp。你可以在dp狀態中記錄有向圖中的4個點每個分別可以走到哪個位置，以及它們的\(val_i\)，但是這樣復雜度非常高，可能是\(n^5\)左右(但是tourist說實現得好是可以過的)。注意到我們只對新圖中基環里所有點的\(val_i\)之和感興趣，而不是對每個狀態的\(val_i\)都感興趣。所以可以先枚舉基環中含有的點的mask，對于每次枚舉用一次dp算出答案。\(dp_{i,u1,u2,u3,u4,sum}\)表示確定了s中的前i個位置填什么，此時0:0,1:0,0:1,1:1分別能走到\(u1,u2,u3,u4\)，在mask中的狀態的\(val\)之和為\(sum\)的方案數。轉移就枚舉s中接下來一個位置填什么，然后根據那個4個點8條邊的有向圖的信息更新dp狀態就可以了，轉移是\(O(1)\)的。最后計算答案的時候，枚舉所有\(u1,u2,u3,u4\)的組合，檢查它們確定的基環樹的基環中的點是否就是mask中那些，如果是就更新答案。
時間復雜度\(O(2^4\cdot 4^4\cdot n^2)\)。看上去計算量挺大，其實如果只訪問可能有效的狀態，是跑得很快的。dp數組要滾動，不然空間可能會爆掉。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353,bas=404;
void add(LL &x,LL y){x+=y;if(x>=MOD) x-=MOD;}
string s;
LL dp[2][810][4][4][4][4],ans1=0,ans2=0,ans3=0,curto[4];
pii to[4][2];
int getCyc()
{
bool vis[4];rep(i,4) vis[i]=false;
vector <int> pth;int cur=0;
while(true)
{
if(vis[cur])
{
rep(i,pth.size()) if(pth[i]==cur)
{
int ret=0;
for(int j=i;j<pth.size();++j) ret|=(1<<pth[j]);
return ret;
}
}
vis[cur]=true;pth.pb(cur);
cur=curto[cur];
}
}
int main()
{
fileio();
to[0][0]=mpr(1,0);to[0][1]=mpr(2,0);
to[1][0]=mpr(0,1);to[1][1]=mpr(3,0);
to[2][0]=mpr(3,0);to[2][1]=mpr(0,-1);
to[3][0]=mpr(0,1);to[3][1]=mpr(0,-1);
cin>>s;
rep(incyc,1<<4) if(incyc>0)
{
LL cnt=__builtin_popcount(incyc);
rep(i,2) rep(j,809) rep(k1,4) rep(k2,4) rep(k3,4) rep(k4,4) dp[i][j][k1][k2][k3][k4]=0;
dp[0][bas][0][1][2][3]=1;
rep(ii,s.size())
{
int i=ii&1,lb=bas-(ii+4)/2*cnt,ub=bas+(ii+4)/2*cnt;
lb=max(lb,0);ub=min(ub,809);
for(int j=lb;j<=ub;++j) rep(k1,4) rep(k2,4) rep(k3,4) rep(k4,4)
{
LL &val=dp[i][j][k1][k2][k3][k4];
if(val==0) continue;
int nk1,nk2,nk3,nk4;
rep(nxt,2) if(s[ii]=='?'||s[ii]==nxt+'a')
{
LL nj=j;
if(incyc&1) nj+=to[k1][nxt].se;nk1=to[k1][nxt].fi;
if(incyc&2) nj+=to[k2][nxt].se;nk2=to[k2][nxt].fi;
if(incyc&4) nj+=to[k3][nxt].se;nk3=to[k3][nxt].fi;
if(incyc&8) nj+=to[k4][nxt].se;nk4=to[k4][nxt].fi;
add(dp[i^1][nj][nk1][nk2][nk3][nk4],val);
}
val=0;
}
}
rep(k1,4) rep(k2,4) rep(k3,4) rep(k4,4)
{
curto[0]=k1;curto[1]=k2;curto[2]=k3;curto[3]=k4;
if(getCyc()==incyc)
{
rep(j,809)
{
if(j<bas) (ans3+=dp[s.size()&1][j][k1][k2][k3][k4])%=MOD;
else if(j==bas) (ans2+=dp[s.size()&1][j][k1][k2][k3][k4])%=MOD;
else (ans1+=dp[s.size()&1][j][k1][k2][k3][k4])%=MOD;
}
}
}
}
cout<<ans1<<endl<<ans2<<endl<<ans3<<endl;
termin();
}
浙公網安備 33010602011771號