「SDOI2017」切树游戏 - 树链剖分维护树形动规+FWT | Bill Yang's Blog

「SDOI2017」切树游戏 - 树链剖分维护树形动规+FWT

题目大意

    小 Q 是一个热爱学习的人,他经常去维基百科学习计算机科学。

    就在刚才,小 Q 认真地学习了一系列位运算符,其中按位异或的运算符$\oplus$ 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律,即 $i \oplus j = j \oplus i$。

    他发现,按位异或可以理解成被运算的数字的二进制位对应位如果相同,则结果的该位置为 $0$,否则为 $1$,例如:$1(01) \oplus 2(10) = 3(11)$。

    他还发现,按位异或可以理解成参与运算的数字的每个二进制位都进行了不进位的加法,例如:$3(11) \oplus 3(11) = 0(00)$。

    现在小 Q 有一棵 $n$ 个结点的无根树 $T$,结点依次编号为 $1$ 到 $n$,其中结点 $i$ 的权值为 $v_i$​。定义一棵树的价值为它所有点的权值的异或和,一棵树 $T$ 的连通子树就是它的一个连通子图,并且这个图也是一棵树。 小 Q 想要在这棵树上玩切树游戏,他会不断做以下两种操作:

  • Change x y,将编号为 $x$ 的结点的权值修改为 $y$。
  • Query k,询问有多少棵 $T$ 的非空连通子树,满足其价值恰好为 $k$。

    小 Q 非常喜(bu)欢(hui)数学,他希望你能快速回答他的问题,你能写个程序帮帮他吗?


题目分析

immortalCO有一篇博客讲了这道题。
但其中有两处错误:

  1. 标题基于变换合并的算法下面第二个式子: 应为
  2. 第三个式子: 应为

然后来讲一讲具体的实现。
首先,将每个权值单项式$z^v$进行FWT,这样异或卷积可以直接点乘起来了。
在回答询问的时候再UFWT回来。

线段树$[x,r]$上的矩阵($r$是链底位置)代表的意义是链底的虚拟结点儿子的向量$\begin{pmatrix}1&0&1\end{pmatrix}$乘上此矩阵可以得到$x$位置的向量。
当然,任意区间$[x,y]$的矩阵是没有意义的,只用来合并转移。
故$[x,r]$上的矩阵$a+c$代表$f$值,$b+d$代表$g$值。

然后套用树剖的套路即可。

下面讲讲细节。

  1. 在$restf,restg$向$f,g$合并的时候,$restf$需要加上$e[0,i]=1$,可能会超过$mod$,而超过$mod$的值是没有求逆元的,因此需要模一下。
  2. 由于消除$restf$的影响时,可能会遇到除以$0$的情况,而$0$是没有逆元的。因此在对$restf$做乘法的时候需要记录一下$0$的个数,在除的时候减少$0$的个数。
  3. 在叶子结点的时候不能“不选自己选子树”,需要特判一下。
  4. 将$m$次循环放在线段树里面($0.4s$出解),放在外面会T($27s$出解)。

不知不觉写了$5k+$,这道毒瘤题出到省选里面出题人也真的是牛逼,大家谨慎做这道题。
不不不,大家快来做这道题啊,又好写又好调。


代码

代码中的$f$与$g$分别代表$restf,restg$。

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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=30005,maxm=128;
const int mod=10007,inv2=5004;

struct FastWalshTransform {
int n;
void init(int n) {
this->n=n;
}
void transform(int *a,int mul) {
for(int len=2; len<=n; len<<=1) {
int mid=len>>1;
for(int *p=a; p!=a+n; p+=len)
for(int i=0; i<mid; i++) {
int x=p[i],y=p[mid+i];
p[i]=(x+y)*mul%mod;
p[mid+i]=(x-y+mod)*mul%mod;
}
}
}
void fwt(int *a) {
transform(a,1);
}
void ufwt(int *a) {
transform(a,inv2);
}
} wtf;

int n,m,pos[maxn],root[maxn],val[maxn],father[maxn],Depth[maxn],Size[maxn],Son[maxn],Top[maxn];
int e[maxn][maxm],g[maxn][maxm],ans[maxm];
bool leaf[maxn];
vector<int> edges[maxn],chain[maxn],tops;
int inv[mod+5];

struct Integer {
int num,cnt;
Integer(int v=0) {
if(v)num=v,cnt=0;
else num=cnt=1;
}
Integer operator * (int v) {
v%=mod;
Integer a=*this;
if(!v)a.cnt++;
else a.num=a.num*v%mod;
return a;
}
Integer operator / (int v) {
v%=mod;
Integer a=*this;
if(!v)a.cnt--;
else a.num=a.num*inv[v]%mod;
return a;
}
void operator *=(int v) {*this=*this*v;}
void operator /=(int v) {*this=*this/v;}
int val() {return cnt?0:num;}
} f[maxn][maxm];

void Dfs1(int Now,int fa,int depth) {
father[Now]=fa;
Depth[Now]=depth;
Size[Now]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Son[Now]]<Size[Next])Son[Now]=Next;
}
if(fa&&edges[Now].size()==1)leaf[Now]=1;
}

void Dfs2(int Now,int top) {
Top[Now]=top;
chain[top].push_back(Now);
if(Now==top)tops.push_back(Now);
if(Son[Now])Dfs2(Son[Now],top);
for(int Next:edges[Now]) {
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
}

struct Tag {
int a,b,c,d;
Tag(int a=1,int b=0,int c=0,int d=0):a(a),b(b),c(c),d(d) {}
int f() {return (a+c)%mod;}
int g() {return (b+d)%mod;}
Tag operator + (const Tag &y) const {
return Tag(a*y.a%mod,(b+a*y.b)%mod,(y.a*c+y.c)%mod,(y.b*c+d+y.d)%mod);
}
};

struct Segment_Tree {
struct Tree {
int left,right;
int lson,rson;
Tag tag[maxm];
Tree(int l=0,int r=0):left(l),right(r),lson(0),rson(0) {}
} tree[maxn<<1];
int size;
#define ls tree[index].lson
#define rs tree[index].rson
#define mid ((left+right)>>1)
void build(int &index,int left,int right,int top) {
if(!index)index=++size;
tree[index]=Tree(left,right);
if(left==right) {
int x=chain[top][left-1];
for(int i=0; i<m; i++) {
int tmp=f[x][i].val()*e[val[x]][i]%mod;
tree[index].tag[i]=Tag(tmp,tmp,leaf[x]?0:tmp,((leaf[x]?0:tmp)+g[x][i])%mod);
}
pos[chain[top][left-1]]=left;
return;
}
build(ls,left,mid,top);
build(rs,mid+1,right,top);
push_up(index);
}
void push_up(int index) {
for(int i=0; i<m; i++)tree[index].tag[i]=tree[rs].tag[i]+tree[ls].tag[i];
}
void update(int index,int target,int x) {
if(target<tree[index].left||target>tree[index].right)return;
if(tree[index].left==tree[index].right) {
for(int i=0; i<m; i++) {
int tmp=f[x][i].val()*e[val[x]][i]%mod;
tree[index].tag[i]=Tag(tmp,tmp,leaf[x]?0:tmp,((leaf[x]?0:tmp)+g[x][i])%mod);
}
return;
}
update(ls,target,x);
update(rs,target,x);
push_up(index);
}
} st;

bool cmp(int x,int y) {
return Depth[x]>Depth[y];
}

void Modify(int x,int v) {
vector<int> lastf,lastg;
int tmp=x;
for(int t; father[t=Top[x]]; x=father[t])
for(int i=0; i<m; i++) {
lastf.push_back(st.tree[root[t]].tag[i].f());
lastg.push_back(st.tree[root[t]].tag[i].g());
}
x=tmp;
int posf=0,posg=0;
val[x]=v;
for(int t; father[t=Top[x]]; x=father[t]) {
st.update(root[t],pos[x],x);
for(int i=0; i<m; i++) {
int lf=lastf[posf++],lg=lastg[posg++];
int tmp=f[x][i].val()*e[val[x]][i]%mod;
f[father[t]][i]/=lf+e[0][i],f[father[t]][i]*=st.tree[root[t]].tag[i].f()+e[0][i];
g[father[t]][i]=(g[father[t]][i]-lg+mod)%mod,g[father[t]][i]=(g[father[t]][i]+st.tree[root[t]].tag[i].g())%mod;
}
}
st.update(root[Top[x]],pos[x],x);
for(int i=0; i<m; i++)ans[i]=st.tree[root[1]].tag[i].g();
wtf.ufwt(ans);
}

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

int main() {
n=Get_Int();
m=Get_Int();
wtf.init(m);
for(int i=0; i<m; i++) {
e[i][i]=1;
wtf.fwt(e[i]);
}
inv[1]=1;
for(int i=2; i<mod; i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1; i<=n; i++) {
val[i]=Get_Int();
for(int j=0; j<m; j++)f[i][j]=1;
}
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1,0,1);
Dfs2(1,1);
sort(tops.begin(),tops.end(),cmp);
for(int x:tops) {
st.build(root[x],1,chain[x].size(),x);
if(father[x])
for(int i=0; i<m; i++) {
f[father[x]][i]*=st.tree[root[x]].tag[i].f()+e[0][i];
g[father[x]][i]=(g[father[x]][i]+st.tree[root[x]].tag[i].g())%mod;
}
}
for(int i=0; i<m; i++)ans[i]=st.tree[root[1]].tag[i].g();
wtf.ufwt(ans);
int q=Get_Int();
while(q--) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int();
if(opt=='C')Modify(x,Get_Int());
else printf("%d\n",(ans[x]+mod)%mod);
}
return 0;
}

姥爷们赏瓶冰阔落吧~
0%