其实考试的时候，考到了这个知识点。发现自己不太会，就赶紧来学一下。
ps：好像学了之后也不会做那道考试题。
前置芝士
- 单位根（FFT用到的那个东西）
- 简单的数学推导基础。
单位根反演
其实也就是一个柿子：
(Large displaystyle qquad [nmid a] = {1over n}sum_{i=0}^{n-1}w_n^{ai})
([n|a]) 表示 (n) 整除 (a) 的时候 ([nmid a]) 的值为 (1), 否则为 (0)。 (w_n^{a_i}) 则表示 (n) 次单位根。
证明的话，也很好证，分两种情况讨论一下就好了,具体如下：
-
当 (a mid n) 即 (amod n eq 0)的时候：
后面的部分其实是个等比数列求和的形式，利用公式可得：
(displaystyle ext{原式} = {1over n}sum_{i=0}^{n-1} w_n^{a_i}= {1over n}left(w_n^{0} imes {1-w_n^{an}over 1-w_n^{a}} ight) = {1over n} left({w_{n}^{0}-w_n^{a_n}over 1-w_n^a } ight))
又因为：(w_n^0 = 1, w_n^{a_n} = 1), 所以 (w_n^{0} - w_{n}^{an} = 0) 。
分子为 (0), 但分母不为 (0), 所以整个柿子的值为 (0) 。
-
当 (amid n) 即 (aequiv 0pmod n) 的时候：
(displaystyle ext{原式} = {1over n}sum_{i=0}^{n-1}w_n^{ai} = {1over n}sum_{i=0}^{n-1} w_{n}^{aipmod n} = {1over n}sum_{i=0}^{n-1} w_{n}^{0} = 1)
有上面的柿子还可以推导出来另外一个柿子：
- ([aequiv bpmod n] = [a-bequiv 0pmod n] = [nmid (a-b)] = displaystyle {1over n}sum_{i=0}w_{n}^{ai-bi} = {1over n}sum_{i=0}^{n-1}w_{n}^{ai}w_{n}^{-b_i})
一般这两个柿子就是单位根反演的常见形式。
例题/应用
求 (left[displaystylesum_{i=0}^{n}{nchoose i} imes s^i imes a_{i ext{mod}4} ight]pmod {998244353}) 的结果。
有一个很显然的做法就是枚举 (a_0,a_1,a_2,a_3) 算他们的系数即：
(displaystylesum_{i=0}^{n}{nchoose i} imes s^i imes a_{i ext{mod}4})
(displaystyle =sum_{i=0}^3a_i sum_{j=0}^{n} [jequiv i ( ext{mod} 4)] imes {nchoose j} imes s^j)
可以发现中间的那个 ([jequiv i ext{mod 4}]) 是单位根反演的柿子，带进去可得：
(原式 = displaystyle{1over 4}sum_{i=0}^3a_isum_{j=0}^{n}{nchoose j} imes s^jsum_{k=0}^{3}w_{4}^{(j-i)k})
(displaystyle ={1over 4}sum_{i=0}^3a_isum_{j=0}^{n}{nchoose j} imes s^jsum_{k=0}^3w_{4}^{jk}w_{4}^{-ik})
交换求和顺序，先枚举 (k) 可得：
(原式 = displaystyle {1over 4}sum_{i=0}^{3}a_isum_{k=0}^{3}w_{4}^{-ik}sum_{j=0}^{n}{nchoose j} imes s^j imes w_{4}^{jk})
不难发现后面的枚举 (j) 的部分是个二项式定理的形式，化简一下可得：
(displaystyle 原式= {1over 4}sum_{i=0}^3a_isum_{k=0}^3w_{4}^{-ik} imes (sw_{4}^k+1)^{n})
由于 (w_{n}^{i} = (g^{p-1over n})^i), 所以快速幂直接算即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int p = 998244353;
int T,n,s,ans,g,inv4,a[5],w[5];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int ksm(int a,int b)
{
int res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
signed main()
{
T = read(); w[0] = 1; inv4 = ksm(4,p-2), g = ksm(3,(p-1)/4);
for(int i = 1; i <= 3; i++) w[i] = w[i-1] * g % p;
while(T--)
{
n = read(); s = read(); ans = 0;
for(int i = 0; i <= 3; i++) a[i] = read();
for(int i = 0; i <= 3; i++)
{
int sum = 0;
for(int j = 0; j <= 3; j++)
{
sum = (sum + ksm(s*w[j]%p+1,n) * ksm(ksm(g,i*j),p-2) % p) % p;
}
ans = (ans + sum * a[i] % p) % p;
}
printf("%lld
",ans*inv4%p);
}
return 0;
}
参考资料： 单位根反演小记