0%

「LOJ 2269」「SDOI2017」切树游戏

LOJ #2269

题意

你有一棵$n$个点的树,点$y$有一个$[0,m)$内的整数权值$a_u$

定义一棵树的权值是点权的异或和

有$q$次操作

  • Change x y,表示把第$x$个点的权值改成$y$

  • Query x,表示询问有多少个非空的联通子树的权值是$x$,模$10007$

$n,q\le30000,m\le128$


分析

一种做法

好像用全局平衡二叉树并不是很快

参考基于变换合并的树上动态DP的链分治算法&SDOI2017 切树游戏(cut)解题报告

没有修改的情况

定义一个联通子树的根是唯一的深度最小的点

令$f_{u,x}$表示以$u$为根权值为$x$的联通子树个数

合并的时候大致是异或卷积

令$F_u(x)$表示$f_{u,* }$的生成函数,定义卷积为异或卷积,有

$$F_u(x)=x^{a_u}\prod_{u\to v}(F_v(x)+x^0)$$

只需要在一开始FWT,过程中的乘法和加法都可以直接做

把每个点的$F$加起来,最后FWT回来得到答案

修改

这里不维护全局的答案

令$g_{u,x}$表示$u$的子树中所有点$v$的$f_{v,x}$之和,$G_u(x)$表示$g_{u,* }$的生成函数,有

$$G_u(x)=F_u(x)+\sum_{u\to v}G_v(x)$$

答案可以从$G_1(x)$中得到

树链剖分后,记$son_u$表示$u$的重儿子

$$LF_u(x)=\prod_{u\to v,v\ne son_u}(F_v(x)+x^0)$$

即轻儿子的合并

同理

$$LG_u(x)=\sum_{u\to v,v\ne son_u}G_v(x)$$

我们用线段树维护$F$和$G$,转移为

$$
\begin{align}
F_u(x)&=x^{a_u}* (F_{son_u}(x)+x^0)* LF_u(x) \
&=x^{a_u}* F_{son_u}(x)* LF_u(x)+x^{a_u}* LF_u(x) \
G_u(x)&=LG_u(x)+G_{son_u}(x)+F_u(x)
\end{align}
$$

就不展开了

把转移看做线性变换

$$
\begin{bmatrix}
LF_u(x)* x^{a_u} & 0 & LF_u(x)* x^{a_u} \
LF_u(x)* x^{a_u} & 1 & LF_u(x)* x^{a_u}+LG_u(x) \
0 & 0 & 1
\end{bmatrix}
\begin{pmatrix}
F_{son_u} \
G_{son_u} \
x^0
\end{pmatrix}
=
\begin{pmatrix}
F_u \
G_u \
x^0
\end{pmatrix}
$$

这样就可以在重链上用线段树维护,轻边上暴力修改

这里维护$LF$的时候需要除法,但是由于取模,不好操作,可以对每个点开一棵线段树维护轻儿子的积

单次修改复杂度$\mathcal O(128\log^2n)$,查询$\mathcal O(128(\log n+\log 128))$

优化

上面转移矩阵的乘法对这种形式封闭

$$
\begin{bmatrix}
a_1 & 0 & b_1 \
c_1 & 1 & d_1 \
0 & 0 & 1 \
\end{bmatrix}
*
\begin{bmatrix}
a_2 & 0 & b_2 \
c_2 & 1 & d_2 \
0 & 0 & 1 \
\end{bmatrix}
=
\begin{bmatrix}
a_1 a_2 & 0 & b_1+a_1 b_2 \
a_2 c_1+c_2 & 1 & b_2 c_1+d_1+d_2 \
0 & 0 & 1 \
\end{bmatrix}
$$

只需要记四个位置就好了

另一种做法

具体的我不会

维护一个全局的答案,每条重链用线段树xjb维护一下,修改的时候暴力增减

好像是不用矩阵的

复杂度一样


代码

不知道为什么常数这么大..

后天就联赛了,还是不卡了

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
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 30005, M = 1<<7, P = 10007;
int num, n, m, invm, id, q, p[N], idfn[N], dfn[N], last[N], a[N], b[N];
int siz[N], top[N], fa[N], h[N], pre[N<<1], e[N<<1];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
inline int Pow(ll x, int y=P-2){
int ans=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
return ans;
}
struct ps{
int f[M];
inline void FWT(int *f, int g){
for(int i=1; i<m; i<<=1) for(int j=0; j<m; j+=i<<1)
for(int k=j; k<j+i; ++k){
int l=f[k], r=f[k+i];
f[k]=l+r, f[k+i]=l-r;
}
for(int i=0; i<m; ++i) f[i]%=P;
if(g==-1) for(int i=0; i<m; ++i) f[i]=f[i]*invm%P;
}
inline void tr(){ FWT(f, 1);}
inline void itr(){ FWT(f, -1);}
inline ps operator +(const ps &rhs)const{
static ps ans;
for(int i=0; i<m; ++i) ans.f[i]=(f[i]+rhs.f[i]);
return ans;
}
inline ps operator -(const ps &rhs)const{
static ps ans;
for(int i=0; i<m; ++i) ans.f[i]=(f[i]-rhs.f[i]);
return ans;
}
inline ps operator *(const ps &rhs)const{
static ps ans;
for(int i=0; i<m; ++i) ans.f[i]=(ll)f[i]*rhs.f[i]%P;
return ans;
}
}st[M], f[N], g[N], lg[N];
struct matrix{
ps a, b, c, d;
inline matrix(){}
inline matrix(const ps &x, const ps &y){ a=b=c=x, d=x+y;}
inline matrix(const ps &A, const ps &B, const ps &C, const ps &D){
a=A, b=B, c=C, d=D;
}
inline matrix operator *(const matrix &rhs)const{
return (matrix){ a*rhs.a, b+a*rhs.b, rhs.a*c+rhs.c, rhs.b*c+d+rhs.d};
}
}s[N<<2];
struct LF{
int n;
ps *s;
void build(int l, int r, int t){
if(l==r) return (void)(s[t]=f[b[l]]+st[0]);
int mid=l+r>>1, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
s[t]=s[k]*s[k|1];
}
inline void init(int cnt){
s=new ps[(cnt+1)<<2];
if(!cnt) s[1]=st[0]; else build(1, n=cnt, 1);
}
void modify(int l, int r, int t, int x, const ps &y){
if(l==r) return (void)(s[t]=y);
int mid=l+r>>1, k=t<<1;
if(x<=mid) modify(l, mid, k, x, y); else modify(mid+1, r, k|1, x, y);
s[t]=s[k]*s[k|1];
}
inline void modify(int x, const ps &y){ modify(1, n, 1, x, y);}
}lf[N];
void dfs1(int u){
siz[u]=1;
f[u]=st[a[u]];
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u]){
fa[e[i]]=u, dfs1(e[i]), siz[u]+=siz[e[i]], f[u]=f[u]*(f[e[i]]+st[0]);
g[u]=g[u]+g[e[i]];
}
g[u]=g[u]+f[u];
}
void dfs2(int u){
idfn[dfn[u]=++id]=u;
int son=0;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u] && siz[e[i]]>siz[son]) son=e[i];
if(son) top[son]=top[u], dfs2(son), last[u]=last[son]; else last[u]=id;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u] && e[i]!=son)
top[e[i]]=e[i], dfs2(e[i]), lg[u]=lg[u]+g[e[i]];

int cnt=0;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u] && e[i]!=son)
b[++cnt]=e[i], p[e[i]]=cnt;
lf[u].init(cnt);
}
void build(int l, int r, int t){
if(l==r){
int u=idfn[l];
s[t]=matrix(lf[u].s[1]*st[a[u]], lg[u]);
return;
}
int mid=l+r>>1, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
s[t]=s[k]*s[k|1];
}
void modify(int l, int r, int t, int x, const matrix &y){
if(l==r) return (void)(s[t]=y);
int mid=l+r>>1, k=t<<1;
if(x<=mid) modify(l, mid, k, x, y); else modify(mid+1, r, k|1, x, y);
s[t]=s[k]*s[k|1];
}
matrix query(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return s[t];
int mid=l+r>>1, k=t<<1;
if(R<=mid) return query(l, mid, k, L, R);
if(L>mid) return query(mid+1, r, k|1, L, R);
return query(l, mid, k, L, R)*query(mid+1, r, k|1, L, R);
}
int main() {
read(n), read(m);
invm=Pow(m);
for(int i=1; i<=n; ++i) read(a[i]);
for(int i=1; i<n; ++i){
static int x, y;
read(x), read(y), add(x, y), add(y, x);
}
for(int i=0; i<m; ++i) st[i].f[i]=1, st[i].tr();

dfs1(1), top[1]=1, dfs2(1);
build(1, n, 1);
read(q);
while(q--){
static char opt;
static int x;
while(isspace(opt=read()));
read(x);
if(opt=='Q'){
ps ans=query(1, n, 1, dfn[1], last[1]).d;
ans.itr();
print((ans.f[x]+P)%P), print('\n');
}
else{
read(a[x]);
while(x){
modify(1, n, 1, dfn[x], matrix(lf[x].s[1]*st[a[x]], lg[x]));
x=top[x];
if(fa[x]){
static matrix tmp;
tmp=query(1, n, 1, dfn[x], last[x]);
lf[fa[x]].modify(p[x], tmp.b+st[0]);
lg[fa[x]]=lg[fa[x]]-g[x];
lg[fa[x]]=lg[fa[x]]+(g[x]=tmp.d);
}
x=fa[x];
}
}
}
return flush(), 0;
}