LG 3321 [SDOI2015]序列统计

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转首先了解原根这里利用到原根的一个性质:设$g$为$m$的一个原根$g^0,g^1,g^2,\dots,g^{\varphi(m)-1}$构成模$m$的简化剩余系这样我们可以把序列中所有数变成原根的次幂,那么序列中所有数的乘积就可以转化为他们的和设这个和为$sum$设生成函数:$\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i$可以发现$f(x)^n$次数为$sum$的那一项的系数就是答案使用快速幂+快速数论变换……