分 類(lèi) 大 討 論
# 題面
給定一棵 \(n\) 個(gè)點(diǎn)的樹(shù)，將其復(fù)制 \(m\) 次得到 \(m+1\) 棵樹(shù)，依次編號(hào)為 \(0\sim m\)。記編號(hào)為 \(i\) 的樹(shù)的節(jié)點(diǎn) \(j\) 為 \((i,j)\)。
令所有 \(m+1\) 棵樹(shù)上的邊都是雙向邊，另外對(duì)于每個(gè) \(i\in[1,m]\)，指定 \(A_i,B_i\)，連一條有向邊：\((i-1,A_i)\to(i,B_i)\)。這樣得到一個(gè)連通的圖。
兩個(gè)玩家 P,Q 在這個(gè)圖上玩游戲：最初 \((0,1)\) 上有一個(gè)棋子，每個(gè)玩家輪流操作，將棋子挪到相鄰的點(diǎn)上。規(guī)定不能挪到已經(jīng)到過(guò)的點(diǎn)，無(wú)法繼續(xù)移動(dòng)的玩家輸?shù)?a href="http://www." target="_blank">游戲。
P 為先手，求有多少種 \(A_1,B_1,A_2,B_2,\dots,A_m,B_m\) 的方案使得 P 必勝。
數(shù)據(jù)規(guī)模：\(1\le n\le10^5,1\le m\le10^{18}\)。
# 解析
可以看出，從樹(shù) \(i-1\) 經(jīng)過(guò)有向邊到達(dá)樹(shù) \(i\) 的點(diǎn) \(B_i\)，就可以看成「把 \(B_i\) 作為第 \(i\) 棵樹(shù)的根，只能向子樹(shù)方向走或走有向邊」這種問(wèn)題。
走有向邊比較復(fù)雜，先不考慮。我們先嘗試求出以點(diǎn) \(1\) 為根，只能向子樹(shù)方向走，每個(gè)點(diǎn)是必勝還是必?cái)?；然后通過(guò)換根 DP 可以得到每個(gè)點(diǎn)為根的答案。
我們可以非常輕松地做一個(gè) DP，求出從點(diǎn) \(i\) 出發(fā)只能朝子樹(shù)方向走，先手是否必勝，記為 \(h_i\)（\(h_i=0\) 即必?cái)。?span id="mrlkstq" class="math inline">\(h_i=1\) 即必勝）。根據(jù)基礎(chǔ)的博弈論知識(shí)，當(dāng) \(u\) 能轉(zhuǎn)移到的所有 \(h_v\) 都為 \(1\)，則 \(h_u=0\)；只要有一個(gè) \(h_v=0\)，則 \(h_u=1\)。
然后考慮加上有向邊 \((i,s)\to (i+1,t)\)。這相當(dāng)于給 \(s\) 新增了一種轉(zhuǎn)移方案，不妨討論一下這個(gè)新增的轉(zhuǎn)移會(huì)對(duì) \(h_s\) 造成什么影響：
- 不難發(fā)現(xiàn)造成的影響只與「\((i+1,t)\) 是必勝還是必?cái) 褂嘘P(guān)，而與 \(t\) 具體是哪個(gè)點(diǎn)無(wú)關(guān)；
- 若 \(t\) 是必?cái)↑c(diǎn)：
- 若 \(h_s=1\)，則 \(s\) 仍然必勝；
- 若 \(h_s=0\)，則 \(s\) 變?yōu)楸貏賾B(tài)。
- 若 \(t\) 是必勝點(diǎn)：
- 若 \(h_s=1\)，則 \(s\) 仍然必勝；
- 若 \(h_s=0\)，則 \(s\) 仍然必?cái) ?/li>
于是我們?cè)俣x一個(gè) \(g_{u,0/1}\)，表示 \(u\) 的子樹(shù)內(nèi)有一條連向下一棵樹(shù)的有向邊，加上這條有向邊后，\(u\) 的狀態(tài)為 \(0\)（必?cái)。? \(1\)（必勝）的方案數(shù)。
雖然在計(jì)算下一棵樹(shù)的答案之前，我們無(wú)法求出 \(g_{u,0/1}\) 的具體值，但是根據(jù)之前的討論，我們知道 \(g\) 的值只與「下一棵樹(shù)在每個(gè)連邊狀態(tài)下，必?cái)↑c(diǎn)的數(shù)量的總和/必勝點(diǎn)的數(shù)量的總和」有關(guān)，因?yàn)橹挥羞@兩個(gè)值決定了 \(t\) 可取的方案數(shù)。
不妨記 \(T_{i,0},T_{i,1}\) 分別表示第 \(i\) 棵樹(shù)在所有狀態(tài)下必?cái)↑c(diǎn)/必勝點(diǎn)數(shù)量的總和。那么 \(g_{u,k}\) 可以表示為：
\[g_{u,k}=g_{u,k,0}T_{i+1,0}+g_{u,k,1}T_{i+1,1}
\] 因?yàn)橐豢脴?shù)只會(huì)連出一條有向邊，所以所有的 \(g_{u,k}\) 都會(huì)是這個(gè)形式——我們可以 DP 計(jì)算出每個(gè)系數(shù) \(g_{u,k,0/1}\)。
這只是以 \(1\) 為根的情況，我們?nèi)匀豢梢該Q根求出「以每個(gè)點(diǎn)為根，要使根為必勝/必?cái)∮卸嗌俜N方案」，記作 \(f_{u,0/1}\)。和 \(g\) 一樣，\(f\) 也是關(guān)于 \(T_{i+1,0},T_{i+1,1}\) 的式子。
然后我們可以得到：
\[\begin{aligned}
T_{i,0}&=\sum_{u=1}^nf_{u,0}=AT_{i+1,0}+BT_{i+1,1}\T_{i,1}&=\sum_{u=1}^nf_{u,1}=CT_{i+1,0}+DT_{i+1,1}
\end{aligned}
\] 不難發(fā)現(xiàn)，對(duì)于每棵樹(shù)，系數(shù) \(A,B,C,D\) 是相同的（每棵樹(shù)的樹(shù)形是一樣的，那么上述DP的轉(zhuǎn)移也都是一樣的，不一樣的是 \(T_{i+1,0},T_{i+1,1}\)，但這和系數(shù)無(wú)關(guān)）。
即：
\[\begin{bmatrix}T_{i,0}\\T_{i,1}\end{bmatrix}
=\begin{bmatrix}A&B\\C&D\end{bmatrix}
\times\begin{bmatrix}T_{i+1,0}\\T_{i+1,1}\end{bmatrix}
\] 計(jì)算的終點(diǎn)在第 \(m\) 棵樹(shù)，因?yàn)樗鼪](méi)有連出的有向邊，可以直接計(jì)算出 \(T_{m,0},T_{m,1}\)。
然后這個(gè)式子就可以矩陣加速，最終復(fù)雜度 \(\mathcal{O}(n+\log m)\)。
唯一的麻煩點(diǎn)在于 \(g\) 的換根 DP。要選擇一個(gè)子樹(shù) \(v\)（或者 \(u\) 本身）連出一條有向邊，則需要考慮除去子樹(shù) \(v\)，剩下的子樹(shù)中是否有必?cái)B(tài)，若有必?cái)B(tài)，則 \(u\) 一定是必勝態(tài)，與 \(v\) 無(wú)關(guān)；否則 \(u\) 的狀態(tài)取決于 \(v\) 連邊后的狀態(tài)。
的確有優(yōu)美的實(shí)現(xiàn)方法，但是我考場(chǎng)上嘗試少寫(xiě)點(diǎn)代碼結(jié)果調(diào)到結(jié)束都還沒(méi)過(guò)大樣例……還不如直接分類(lèi)大討論……
# 源代碼
不建議借鑒這份代碼 (;′⌒`)
點(diǎn)擊展開(kāi)/折疊代碼
開(kāi)幕雷擊[doge]
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<class T>inline T rin(T &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
const int N=1e5+10,MOD=1e9+7;
typedef long long llong;
#define con(type) const type &
inline int add(con(int)a,con(int)b){return a+b>=MOD?a+b-MOD:a+b;}
inline int sub(con(int)a,con(int)b){return a-b<0?a-b+MOD:a-b;}
inline int mul(con(int)a,con(int)b){return int(1ll*a*b%MOD);}
inline int ina_pow(con(int)a,con(int)b){return b?mul(ina_pow(mul(a,a),b>>1),(b&1)?a:1):1;}
inline int inv(con(int)key){return ina_pow(key,MOD-2);}
struct Graph{
int head[N],to[N<<1],nxt[N<<1],ncnt;
void addEdge(con(int)u,con(int)v){
int p=++ncnt,q=++ncnt;
to[p]=v,nxt[p]=head[u],head[u]=p;
to[q]=u,nxt[q]=head[v],head[v]=q;
}
inline int operator [](con(int)u){return head[u];}
}gr;
struct Data{
int sum0,sum1;
Data(){sum0=sum1=0;}
Data(con(int)_sum0,con(int)_sum1):sum0(_sum0),sum1(_sum1){}
Data operator +(con(Data)b)const{return Data(add(sum0,b.sum0),add(sum1,b.sum1));}
Data operator -(con(Data)b)const{return Data(sub(sum0,b.sum0),sub(sum1,b.sum1));}
Data operator *(con(int)d)const{return Data(mul(sum0,d),mul(sum1,d));}
friend Data operator *(con(int)b,con(Data)a){return Data(mul(a.sum0,b),mul(a.sum1,b));}
void operator +=(con(Data)b){(*this)=(*this)+b;}
void operator -=(con(Data)b){(*this)=(*this)-b;}
void operator *=(con(int)b){(*this)=(*this)*b;}
int value(con(int)c0,con(int)c1){return add(mul(sum0,c0),mul(sum1,c1));}
// void debug()const{printf("(%d,%d)",sum0,sum1);}
};
int n,tot_win,tot_los;
llong m;
Data g[N][2],f[N][2];
int h[N],zerotyp[N];
// int wtfdebug[N];
// h[i]=0 loser ; h[i]=1 winner
void dpDFS(con(int)u,con(int)fa){
int cnt_los=0;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
dpDFS(v,u);
cnt_los+=!h[v];
}
h[u]=cnt_los>0;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
if(cnt_los-(!h[v])) // already win
g[u][1]+=g[v][0]+g[v][1];
else{
g[u][0]+=g[v][1];
g[u][1]+=g[v][0];
}
}
if(cnt_los) g[u][1]+=Data(1,1);
else g[u][0]+=Data(0,1),g[u][1]+=Data(1,0);
}
void rootDFS(con(int)u,con(int)fa,con(int)ph,Data *pg){
int cnt_los=!ph;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
cnt_los+=!h[v];
}
tot_win+=cnt_los>0;
tot_los+=cnt_los==0;
// wtfdebug[u]=cnt_los;
if(!cnt_los){
Data gwin=pg[0],glos=pg[1];
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
gwin+=g[v][0],glos+=g[v][1];
}
gwin+=Data(1,0),glos+=Data(0,1);
f[u][0]=glos,f[u][1]=gwin;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
Data nowg[2]={glos-g[v][1],gwin-g[v][0]};
rootDFS(v,u,0,nowg);
}
}
else if(cnt_los==1){
Data gwin,gwinsp,glos,glossp;
// sp: if transform to v ('h[v]==0')
if(!ph) gwin+=pg[0],glos=pg[1];
else{
gwinsp+=pg[0],glossp+=pg[1];
gwin+=pg[0]+pg[1];
}
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
if(!h[v]) gwin+=g[v][0],glos+=g[v][1];
else{
gwinsp+=g[v][0],glossp+=g[v][1];
gwin+=g[v][0]+g[v][1];
}
}
gwinsp+=Data(1,0),glossp+=Data(0,1);
gwin+=Data(1,1);
f[u][0]=glos,f[u][1]=gwin;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
Data nowg[2];
if(h[v]){
nowg[0]=glos;
nowg[1]=gwin-(g[v][0]+g[v][1]);
rootDFS(v,u,1,nowg);
}
else{
nowg[0]=glossp,nowg[1]=gwinsp;
rootDFS(v,u,0,nowg);
}
}
}
else if(cnt_los==2){
Data gwin,glos,gwinsp,glossp;
if(!ph) gwin+=pg[0]+pg[1],gwinsp+=pg[0],glossp+=pg[1];
else gwin+=pg[0]+pg[1],gwinsp+=pg[0]+pg[1];
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
if(!h[v]) gwin+=g[v][0]+g[v][1],gwinsp+=g[v][0],glossp+=g[v][1];
else gwin+=g[v][0]+g[v][1],gwinsp+=g[v][0]+g[v][1];
}
gwin+=Data(1,1);
gwinsp+=Data(1,1);
f[u][0]=glos,f[u][1]=gwin;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
Data nowg[2];
if(!h[v]){
nowg[0]=glossp-g[v][1];
nowg[1]=gwinsp-g[v][0];
rootDFS(v,u,1,nowg);
}
else{
nowg[0]=glos,nowg[1]=gwin-g[v][0]-g[v][1];
rootDFS(v,u,1,nowg);
}
}
}
else{
Data gwin,glos;
gwin+=pg[0]+pg[1];
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
gwin+=g[v][0]+g[v][1];
}
gwin+=Data(1,1);
f[u][0]=glos,f[u][1]=gwin;
for(int it=gr[u];it;it=gr.nxt[it]){
int v=gr.to[it];
if(v==fa) continue;
Data nowg[2];
nowg[0]=glos,nowg[1]=gwin-g[v][0]-g[v][1];
rootDFS(v,u,1,nowg);
}
}
}
void multi(int a[2][2],int b[2][2]){
int c[2][2]={};
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c[i][j]=add(c[i][j],mul(a[i][k],b[k][j]));
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
a[i][j]=c[i][j];
}
int main(){
// freopen("tree\\tree3.in","r",stdin);
rin(n),rin(m);
for(int i=1,u,v;i<n;i++)
gr.addEdge(rin(u),rin(v));
dpDFS(1,0);
Data nowg[2];
rootDFS(1,0,1,nowg);
Data trlos,trwin;
for(int i=1;i<=n;i++)
trlos+=f[i][0],trwin+=f[i][1];
int mat[2][2]={{trlos.sum0,trlos.sum1},{trwin.sum0,trwin.sum1}},res[2][2]={{1,0},{0,1}};
m--;
while(m){
if(m&1) multi(res,mat);
multi(mat,mat),m>>=1;
}
int res_win=add(mul(res[1][0],tot_los),mul(res[1][1],tot_win)),
res_los=add(mul(res[0][0],tot_los),mul(res[0][1],tot_win));
printf("%d\n",f[1][1].value(res_los,res_win));
return 0;
}
THE END
Thanks for reading!
琴弦上羽徵角商角 羽徵角商角
不知何時(shí)才能到下一闋
琴聲下你是月上月 你是月上月
比長(zhǎng)夜中月色更皎潔
琴瑟間曲辭疊上疊 曲辭疊上疊
游走過(guò)的繞梁聲不停歇
讓我的心
似浮萍隨 漣漪搖曳
——《琴弦上(vocaloid)》By 樂(lè)正綾/赤羽/星葵
> Link 琴弦上-Bilibili
|
