数学 原根 P8323题解

· · 题解

为了我，歌唱吧，歌唱吧，歌唱吧！！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)];