「SOL」星际迷航(LOJ)

分 类 大 讨 论


# 题面

给定一棵 \(n\) 个点的树,将其复制 \(m\) 次得到 \(m+1\) 棵树,依次编号为 \(0\sim m\)。记编号为 \(i\) 的树的节点 \(j\) 为 \((i,j)\)。

令所有 \(m+1\) 棵树上的边都是双向边,另外对于每个 \(i\in[1,m]\),指定 \(A_i,B_i\),连一条有向边:\((i-1,A_i)\to(i,B_i)\)。这样得到一个连通的图。

两个玩家 P,Q 在这个图上玩游戏:最初 \((0,1)\) 上有一个棋子,每个玩家轮流操作,将棋子挪到相邻的点上。规定不能挪到已经到过的点,无法继续移动的玩家输掉游戏。

P 为先手,求有多少种 \(A_1,B_1,A_2,B_2,\dots,A_m,B_m\) 的方案使得 P 必胜。

数据规模:\(1\le n\le10^5,1\le m\le10^{18}\)。


# 解析

可以看出,从树 \(i-1\) 经过有向边到达树 \(i\) 的点 \(B_i\),就可以看成「把 \(B_i\) 作为第 \(i\) 棵树的根,只能向子树方向走或走有向边」这种问题。

走有向边比较复杂,先不考虑。我们先尝试求出以点 \(1\) 为根,只能向子树方向走,每个点是必胜还是必败;然后通过换根 DP 可以得到每个点为根的答案。

我们可以非常轻松地做一个 DP,求出从点 \(i\) 出发只能朝子树方向走,先手是否必胜,记为 \(h_i\)(\(h_i=0\) 即必败,\(h_i=1\) 即必胜)。根据基础的博弈论知识,当 \(u\) 能转移到的所有 \(h_v\) 都为 \(1\),则 \(h_u=0\);只要有一个 \(h_v=0\),则 \(h_u=1\)。

然后考虑加上有向边 \((i,s)\to (i+1,t)\)。这相当于给 \(s\) 新增了一种转移方案,不妨讨论一下这个新增的转移会对 \(h_s\) 造成什么影响:

  • 不难发现造成的影响只与「\((i+1,t)\) 是必胜还是必败」有关,而与 \(t\) 具体是哪个点无关;
  • 若 \(t\) 是必败点:
    • 若 \(h_s=1\),则 \(s\) 仍然必胜;
    • 若 \(h_s=0\),则 \(s\) 变为必胜态。
  • 若 \(t\) 是必胜点:
    • 若 \(h_s=1\),则 \(s\) 仍然必胜;
    • 若 \(h_s=0\),则 \(s\) 仍然必败。

于是我们再定义一个 \(g_{u,0/1}\),表示 \(u\) 的子树内有一条连向下一棵树的有向边,加上这条有向边后,\(u\) 的状态为 \(0\)(必败)/ \(1\)(必胜)的方案数。

虽然在计算下一棵树的答案之前,我们无法求出 \(g_{u,0/1}\) 的具体值,但是根据之前的讨论,我们知道 \(g\) 的值只与「下一棵树在每个连边状态下,必败点的数量的总和/必胜点的数量的总和」有关,因为只有这两个值决定了 \(t\) 可取的方案数。

不妨记 \(T_{i,0},T_{i,1}\) 分别表示第 \(i\) 棵树在所有状态下必败点/必胜点数量的总和。那么 \(g_{u,k}\) 可以表示为:

\[g_{u,k}=g_{u,k,0}T_{i+1,0}+g_{u,k,1}T_{i+1,1} \]

因为一棵树只会连出一条有向边,所以所有的 \(g_{u,k}\) 都会是这个形式——我们可以 DP 计算出每个系数 \(g_{u,k,0/1}\)。

这只是以 \(1\) 为根的情况,我们仍然可以换根求出「以每个点为根,要使根为必胜/必败有多少种方案」,记作 \(f_{u,0/1}\)。和 \(g\) 一样,\(f\) 也是关于 \(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} \]

不难发现,对于每棵树,系数 \(A,B,C,D\) 是相同的(每棵树的树形是一样的,那么上述DP的转移也都是一样的,不一样的是 \(T_{i+1,0},T_{i+1,1}\),但这和系数无关)。

即:

\[\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} \]

计算的终点在第 \(m\) 棵树,因为它没有连出的有向边,可以直接计算出 \(T_{m,0},T_{m,1}\)。

然后这个式子就可以矩阵加速,最终复杂度 \(\mathcal{O}(n+\log m)\)。

唯一的麻烦点在于 \(g\) 的换根 DP。要选择一个子树 \(v\)(或者 \(u\) 本身)连出一条有向边,则需要考虑除去子树 \(v\),剩下的子树中是否有必败态,若有必败态,则 \(u\) 一定是必胜态,与 \(v\) 无关;否则 \(u\) 的状态取决于 \(v\) 连边后的状态。

的确有优美的实现方法,但是我考场上尝试少写点代码结果调到结束都还没过大样例……还不如直接分类大讨论……


# 源代码

不建议借鉴这份代码 (;′⌒`)

点击展开/折叠代码

开幕雷击[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!

琴弦上羽徵角商角 羽徵角商角
不知何时才能到下一阕
琴声下你是月上月 你是月上月
比长夜中月色更皎洁
琴瑟间曲辞叠上叠 曲辞叠上叠
游走过的绕梁声不停歇
让我的心
似浮萍随 涟漪摇曳

——《琴弦上(vocaloid)》By 乐正绫/赤羽/星葵

> Link 琴弦上-Bilibili

上一篇:数据结构10 Network Flow Problems


下一篇:JQuery样式滚筒条