自动搬运

查看原文

来自洛谷，原作者为

	Prean 不断倒下，不断站起来，不停地与自己作斗争

搬运于2025-08-24 22:38:00，当前版本为作者最后更新于2022-05-04 21:10:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为了我，歌唱吧，歌唱吧，歌唱吧！！1（大雾）

Subtask1

暴力，可以获得 $7$ 分的高分！

Subtask2

注意到只有一个询问，也就只有一个点值。

点值的性质有两个：$f(k)\times g(k)=(f\times g)(k),f(k)+g(k)=(f+g)(k)$。

我们假设询问的那个点在第 $d$ 层，那么我们对第 $d-1$ 层维护多项式在 $k^2$ 处的点值，对于第 $d-t$ 层维护多项式在 $k^{2^{t}}$ 处的点值。

Subtask3

这一档部分分是为 NTT 留的。

注意到可以不用复合 $x^2$，只要在最后计算在 $k^{2^{d}}$ 处的点值即可。暴力计算就行。

Subtask4

因为询问求的是点值，那么我们就对所有节点维护点值吧。

多项式乘法的本质是点值，DFT 计算的就是点值，所以考虑对所有节点上的多项式做一个长度为 $mod-1$ 的 DFT。

即求出 $F_v(g^k)$。

注意到每次平方的时候会有 $(+x)^2=(-x)^2$，也就是说会出现不同的点但是值相同的情况。

并且再次注意到对于每一层相当于出现了一个 $len[d]$ 有 $F_v(g^k)=F_v(g^{k\bmod len[d]})$，也就是说有一个循环节。

直接维护这个循环节就好了，多项式的点值乘起来和加起来都是 $O(1)$的，总复杂度 $O(d\times mod+\sum q)$。

标算核心部分：

while(m--){
	u=read();v=read();if(vis[u][v]==T)continue;vis[u][v]=T;
	F[now][v][0]=(F[now][v][0]+1ull*F[now^1][u][0]*F[now^1][u][0])%mod;
	for(i=1;i<len;++i)F[now][v][i]=(F[now][v][i]+1ull*F[now^1][u][i<<1]*F[now^1][u][i<<1])%mod;
}
while(q--)u=read(),v=read(),ans^=q*F[now^1][u][lg[v]%(len<<1)];