0%

LOJ 2269. 「SDOI2017」切树游戏

LOJ 2269. 「SDOI2017」切树游戏

给一棵$n$个点的树,点有点权且小于$m$。定义一个连通块的权值为点权异或和。

$Q$次操作,单点修改点权或询问满足权值为$x$的非空连通块数量,模$10007$

$n,Q\le 3\times 10^4,m\le 128$

【FWT】【生成函数】【动态dp】

暴力dp:令$f(u,x)$表示$u$的子树中包含$u$且权值为$x$的连通块数量。考虑加入一个孩子$v$ :

直接做是$O(n^2m^2)$.最后$ans(x)=\sum_uf(u,x)$

异或卷积直接呼一个FWT上去就变成$O(n^2m\log m)$,事实上一开始FWT掉之后直接对着点值做,最后IFWT回去就能$O(n^2m)$.

考虑优化。按照套路我们先考虑生成函数,$F_u=\sum_{i=0}^{m-1}f(u,i)x^i,S_u=\sum_{v\in sub(u)}\sum_{i=0}^{m-1}f(v,i)x^i$.

然后。。就可以复习动态dp了。

记$LF_u$为轻儿子的$\prod (F_v+1)$,$LS_u$为轻儿子的$\sum S_v$,那么:

这东西就很经典了,写成矩阵:

然后就动态dp,求出根的矩阵之后IFWT回去。

复杂度$\mathcal O(Qm(\log n+\log m) )$

注意这里$3\times 3$的矩阵做乘法有规律,只有4个位置可能会变化,只算那四个就好了。

还有一个细节是,重新计算$LF$的时候可能会出现除以0的情况,而0没有逆元,因此可以记录一下有几个0,这样就能重新计算$LF$了。

我用LCT实现的代码:Code