知识精要
单位根反演用于计算一个数列中所有 (k) 的倍数的和。
具体方法是，我们构造一个多项式，其系数为数列。for(i = 0 -> n - 1)，将 (omega_k^i) 代入我们构造的多项式，值的和即为答案。
看起来复杂度更差，但是“构造多项式”可能会有一种能更快计算的“封闭形式”（比如二项式定理），能显著优化复杂度。
证明需要两个式子：
[[k|n] = frac{1}{k} sum_{i=0}^{k-1}w_k^{in}
]
（显然）
一看就是等比数列求和，直接套用公式推一推就出来了。
[sum_{i=0}^n [k|i]a_i = frac{1}{k}sum_{j=0}^{k-1}f(w_k^j)
]
给一个简单的推导：
[sum_{i=0}^n[k|i]a_i
]
[=sum_{i=0}^nsum_{j=0}^{k-1}1/k * w_k^{ij}a_i
]
[=frac{1}{k} sum_{j=0}^{k-1}sum_{i=0}^na_iw_k^{ji}
]
[=frac{1}{k}sum_{j=0}^{k-1}f(w_k^j)
]
技能展示
#6485. LJJ 学二项式定理
输入以下变量的值：$ n, s , a_0 , a_1 , a_2 , a_3$，求以下式子的值：
[left[ sum_{i=0}^n left( {nchoose i} cdot s^{i} cdot a_{imod 4}
ight)
ight] mod 998244353
]
将每个 (a_i) 分开考虑。对于每个 (a_i)，我们要算的是：
[sum_{i=0}^n( {nchoose i} s^i)[i mod 4 = ...]
]
对于 (a_0) 比较好算，直接二项式定理搞上去即可。主要是算 (a_{1,2,3})。
根据生成函数的基本运算，(f(x)/x) 能够达到系数“左移”一位的效果，据此可以计算 (a_{1,2,3})。
代码：
ll g[4] = {1, 911660635, 998244352, 86583718};
inline ll calc(ll x) {
return quickpow(s * x % P + 1, n);
}
inline void work() {
read(n), read(s);
for (register int i = 0; i < 4; ++i) read(a[i]), a[i] %= P;
n %= (P - 1);
s %= P;
ll ans = 0;
for (register int i = 0; i < 4; ++i) {
ll res = 0;
for (register int j = 0; j < 4; ++j) {
res += calc(g[j]) * inv(quickpow(g[j], i)) % P;
}
ans += a[i] * res % P;
}
ans = (ans % P + P) % P;
ans = ans * inv(4) % P;
printf("%lld
", ans);
}
P5293 [HNOI2019]白兔之舞
还不会...