「SOL」星际迷航(LOJ) | Lucky_Glass's Blog
0%

「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}$ 都会是这个形式——我们可以 DP 计算出每个系数 $g_{u,k,0/1}$。

这只是以 $1$ 为根的情况,我们仍然可以换根求出「以每个点为根,要使根为必胜/必败有多少种方案」,记作 $f_{u,0/1}$。和 $g$ 一样,$f$ 也是关于 $T_{i+1,0},T_{i+1,1}$ 的式子。

然后我们可以得到:

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

即:

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

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

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

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


# 源代码

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

点击展开/折叠代码

开幕雷击[doge]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
/*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