单位根反演
通常用于求 \(\sum\limits_{i=0}^n[x\mid i]f_i\)。
形式
\[[n\mid k]=\frac{1}{n}\sum\limits_{i=0}^{n-1}\omega_n^{ik} \]其中 \(\omega_n\) 是 \(n\) 次单位根，模意义下可以被原根替换。
证明
当 \(n\mid k\) 时，\(\omega_n^{ki}=1\)。所以右边等于 \(\frac{1}{n}\sum\limits_{i=0}^{n-1}1=1\)。
当 \(n\nmid k\) 时，右边等比数列求和：
\[\frac{1}{n}\times\frac{\omega_n^{nk}-1}{\omega_n^k-1} \]因为 \(\omega_n^{nk}=1\) 所以柿子等于 \(0\)。
推论
一个更加常用的形式：设 \(F(x)=\sum\limits_{i=0}^nf_ix^i\)，有
\[\sum\limits_{i=0}^n[p\mid i]f_i=\frac{1}{p}\sum\limits_{j=0}^{p-1}F(\omega_p^j) \]从原形式推一下就行。
LibreOJ #6485
给定 \(T\le10^5\) 组 \(n,s,a_0,a_1,a_2,a_3\)，求
\[\large{[\sum\limits_{i=0}^n(\binom{n}{i}\cdot s^i\cdot a_{i\space\bmod\space4})]\space\bmod\space998244353} \]\(1\le n\le10^{18},1\le s,a_0,a_1,a_2,a_3\le10^8\)。
对 \(i\equiv0,1,2,3(\bmod\space4)\) 分类讨论：
当 \(i\equiv0(\bmod\space4)\) 时：
即求 \(S_0=a_0\sum\limits_{i=0}^n[4\mid i]\binom{n}{i}s^i\)。
构造 \(F_0(x)=(sx+1)^n\)，单位根反演，\(S_0=\frac{a_0}{4}\sum\limits_{j=0}^3F_0(g^j)\)，其中 \(g\) 是 \(\bmod\space998244353\) 的 \(4\) 次单位根。
当 \(i\equiv1(\bmod\space4)\) 时：
即求 \(S_1=a_1\sum\limits_{i=0}^n[4\mid(i-1)]\binom{n}{i}s^i\)
构造 \(F_1(x)=\frac{F_0(x)}{x}=\sum\limits_{i=0}^n\binom{n}{i}\cdot s^i\cdot x^{i-1}\)，那么 \(S_1=\frac{a_1}{4}\sum\limits_{j=0}^3F_1(g^j)\)。
\(i\equiv2(\bmod\space4)\) 和 \(i\equiv3(\bmod\space4)\) 的情况类似。
Code
#include <bits/stdc++.h>
const int mod = 998244353;
using ia = long long;
int T;
ia n, s, a[4];
inline ia qpow(ia b, ia p) {
ia res = 1;
for (; p; p >>= 1) {
if (p & 1)
res = res * b % mod;
b = b * b % mod;
}
return res;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &n, &s);
for (int i = 0; i < 4; i++)
scanf("%lld", &a[i]);
ia G = qpow(3, (mod - 1) >> 2);
ia S[4] = {0, 0, 0, 0};
for (int j = 0; j < 4; j++) {
ia x = qpow(G, j);
ia inv_x = qpow(x, mod - 2);
for (int i = 0; i < 4; i++)
(S[i] += qpow((s * x + 1) % mod, n) * qpow(inv_x, i)) %= mod;
}
for (int j = 0; j < 4; j++)
S[j] = S[j] * a[j] % mod * qpow(4, mod - 2) % mod;
std::cout << (S[0] + S[1] + S[2] + S[3]) % mod << '\n';
}
return 0;
}