单位根反演小记
command_block
2019-11-12 21:04:13
首先您需要知道单位根是个什么东西 : [傅里叶变换(FFT)学习笔记](https://www.luogu.org/blog/command-block/fft-xue-xi-bi-ji)
先抛一个等式:
**①** $[n|a]=\dfrac{1}{n}\sum\limits_{k=0}^{n-1}w_n^{ak}$
**证明** :
- $a≠0\pmod n$
使用等比数列求和。
原式 $=\dfrac{1}{n}\sum\limits_{k=0}^{n-1}w_n^{ak}=\dfrac{1}{n}*\dfrac{w_n^{an}-1}{w_n^a-1}$
又因为 $w_n^{a}-1=w_n^0-1=0$ ,且 $w_n^a-1≠0$ 所以式子的值为 $0$。
- $a=0\pmod n$
等比数列求和在公比为 $1$ 时需要特判。
原式$=\dfrac{1}{n}\sum\limits_{k=0}^{n-1}w_n^{ak\bmod n}=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{0}=1$
可以导出下式
- **②** $[a=b\pmod n]=[a-b=0\pmod n]=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{(a-b)k}=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{ak}w_n^{-bk}$
## 应用①
- 和$\mod\ $有关的一系列东西。
例题 : [Loj#6485. LJJ 学二项式定理](https://loj.ac/problem/6485)
求$\large\sum\limits_{i=0}^n\dbinom{n}{i}s^ia_{i\mod 4}$
$=\sum\limits_{i=0}^n\dbinom{n}{i}s^i\sum\limits_{j=0}^3 a_j[i\mod 4=j]$
通过上面的结论可知 $[i\mod 4=j]=[4|i-j]=\dfrac{1}{4}\sum\limits_{k=0}^3w_4^{k(i-j)}$
$=\dfrac{1}{4}\sum\limits_{i=0}^n\dbinom{n}{i}s^i\sum\limits_{j=0}^3 a_j\sum\limits_{k=0}^3w_4^{k(i-j)}$
$=\dfrac{1}{4}\sum\limits_{j=0}^3 a_j\sum\limits_{i=0}^n\dbinom{n}{i}s^i\sum\limits_{k=0}^3w_4^{ki}w_4^{-kj}$
$=\dfrac{1}{4}\sum\limits_{j=0}^3 a_j\sum\limits_{k=0}^3w_4^{-kj}\sum\limits_{i=0}^n\dbinom{n}{i}s^iw_4^{ki}$
后面的一部分就能够使用二项式定理了 :
$\sum\limits_{i=0}^n\dbinom{n}{i}s^iw_4^{ki}=\sum\limits_{i=0}^n\dbinom{n}{i}(sw_4^k)^i1^{n-i}=(sw_4^k+1)^n$
原式$=\dfrac{1}{4}\sum\limits_{j=0}^3 a_j\sum\limits_{k=0}^3w_4^{-kj}(sw_4^k+1)^n$
众所周知$998244353$的原根是3,那么$w_4^1=g^{(mod-1)/4}$。
剩下的就一个快速幂了。
```cpp
#include<algorithm>
#include<cstdio>
#define mod 998244353
#define ll long long
using namespace std;
ll powM(ll a,int t=mod-2)
{
ll ans=1;
while(t){
if (t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
const ll w[4]={1,911660635,998244352,86583718};
int a[5];
ll n,s,inv4=powM(4);
void solve()
{
scanf("%lld%lld%d%d%d%d",&n,&s,a,a+1,a+2,a+3);
n%=(mod-1);
ll ans=0,sum;
for (int i=0;i<4;i++){
sum=0;
for (int j=0;j<4;j++)
sum=(sum+w[((4-i)*j)&3]*powM(s*w[j]%mod+1,n))%mod;
ans=(ans+sum*a[i])%mod;
}printf("%lld\n",ans*inv4%mod);
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
[P5591 小猪佩奇学数学](https://www.luogu.org/problem/P5591)
给定 $n,p,k$,询问
$$
\sum\limits_{i=0}^n \binom n i \times p^{i} \times \left\lfloor \dfrac{i}{k} \right\rfloor \bmod 998244353
$$
$k \in \{2^{w}|0 \leq w \leq 20\}$
首先这个整除一看就不可做的样子……
抖个机灵 : $\left\lfloor \dfrac{i}{k} \right\rfloor=\dfrac{i-i\ \bmod\ k}{k}$
那么原式$=\dfrac{1}{k}\sum\limits_{i=0}^n \dbinom{n}{i}p^{i}(i-i\ \bmod\ k)$
前面的$\dfrac{1}{k}$暂且忽略。
$=\sum\limits_{i=0}^n \dbinom{n}{i}p^{i}i-\sum\limits_{i=0}^n \dbinom{n}{i}p^{i}(i\ \bmod\ k)$
- 左半边的部分
$=\sum\limits_{i=0}^n \dbinom{n}{i}p^{i}i$
最右边的$i$并不好直接处理,考虑用组合数吸收掉。
结论:$\dbinom{n}{m}m=\dbinom{n-1}{m-1}n$ ,拆开组合数就能证明了。
原式$=np\sum\limits_{i=0}^n \dbinom{n-1}{i-1}p^{i-1}=np(p+1)^{n-1}$
- 右半边的部分
$=\sum\limits_{i=0}^n\dbinom{n}{i}p^{i}(i\ \bmod\ k)$
$=\dfrac{1}{k}\sum\limits_{i=0}^n\dbinom{n}{i}p^{i}\sum\limits_{j=0}^{k-1}j[i\ \bmod\ k==j]$
前面的$\dfrac{1}{k}$先忽略不看。
$=\sum\limits_{i=0}^n\dbinom{n}{i}p^{i}\sum\limits_{j=0}^{k-1}j\sum\limits_{t=0}^{k-1}w_k^{t(i-j)}$
$=\sum\limits_{j=0}^{k-1}j\sum\limits_{t=0}^{k-1}w_k^{-tj}\sum\limits_{i=0}^n\dbinom{n}{i}p^{i}w_k^{ti}$
$=\sum\limits_{j=0}^{k-1}j\sum\limits_{t=0}^{k-1}w_k^{-tj}(1+pw_k^t)^n$
(到这里已经得到一个$O(k^2)$做法)后面的一坨不太好算,给扔到前面去。
$=\sum\limits_{t=0}^{k-1}(1+pw_k^t)^n\sum\limits_{j=0}^{k-1}jw_k^{-tj}$
这时后面的$\sum\limits_{j=0}^{k-1}jw_k^{-tj}$看起来比较好做。
> 设$S(n,k)=\sum\limits_{i=0}^{n-1}ik^i$
> $kS(n,k)-S(n,k)=\sum\limits_{i=0}^{n-1}ik^{i+1}-\sum\limits_{i=0}^{n-1}ik^i$
> $=\sum\limits_{i=1}^{n}(i-1)k^{i}-\sum\limits_{i=0}^{n-1}ik^i$
> $=-\sum\limits_{i=1}^{n-1}k^{i}+(n-1)k^{n}$
> $=\dfrac{1-k^{n+1}}{k-1}+1+(n-1)k^{n}$
> 综上可解得$S(n,k)=\dfrac{\dfrac{1-k^{n}}{k-1}+(n-1)k^{n}+1}{k-1}$
> 注意到带入的$k$总是$n$次单位根,那么$k^n=1$。
> $S(n,k)=\dfrac{n}{k-1}$
> 注意上述推导要求$k≠1$,如果$k=1$可得
> $S(n,1)=\sum\limits_{i=0}^{n}i=\dfrac{(n-1)n}{2}$
> 任意$S$函数都可以$O(logn)$内计算出来。
原式$=\sum\limits_{t=0}^{k-1}(1+pw_k^t)^nS(k-1,w_k^{-t})$
这就是一个$O(klogn)$的解法。
```cpp
#include<algorithm>
#include<cstdio>
#define mod 998244353
#define ll long long
using namespace std;
ll powM(ll a,int t=mod-2)
{
ll ans=1;
while(t){
if (t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int n,p,k;
ll w[1100000];
inline ll S(ll n,ll k)
{
if (k==1)return ((n-1)*n>>1)%mod;
return n*powM(k-1)%mod;
}
int main()
{
scanf("%d%d%d",&n,&p,&k);
ll buf=powM(3,(mod-1)/k),ans=0;
w[0]=1;
for (int i=1;i<=k;i++)
w[i]=w[i-1]*buf%mod;
for (int i=0;i<k;i++)
ans=(ans+powM((p*w[i]+1)%mod,n)*S(k,w[k-i]))%mod;
ans=ans*powM(k)%mod;
ans=(1ll*n*p%mod*powM(p+1,n-1)-ans+mod)%mod;
printf("%lld",ans*powM(k)%mod);
return 0;
}
```
**附加练习**:
- [[数学记录]Uoj#450. 【集训队作业2018】复读机](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-450-ji-xun-dui-zuo-ye-2018-fu-du-ji)
## 应用②
- $IDFT$中用于证明正确性。
- 某些需要用到单位根的题目里面可以用来反演/构造。
- 计算循环卷积
循环卷积即形为 :
$$P[k]=\sum\limits_{i=0,j=0}^n[(i+j)\bmod n=k]F[i]G[j]$$
$$=\sum\limits_{i=0,j=0}^n[(i+j-k)=0\!\!\!\!\pmod n]F[i]G[j]$$
$$=\sum\limits_{i=0,j=0}^n\dfrac{1}{n}\sum\limits_{t=0}^{n-1}w_n^{(i+j-k)t}F[i]G[j]$$
$$=\dfrac{1}{n}\sum\limits_{t=0}^{n-1}w_n^{-kt}\sum\limits_{i=0,j=0}^nw_n^{it}w_n^{jt}F[i]G[j]$$
把独立的部分组合起来
$$=\dfrac{1}{n}\sum\limits_{t=0}^{n-1}w_n^{-kt}\left(\sum\limits_{i=0}^nw_n^{it}F[i]\right)\left(\sum\limits_{i=0}w_n^{jt}G[j]\right)$$
设$F_{DFT}[k]=\sum\limits_{i=0}^nw_n^{ik}F[i]$ , $G_*$ 同理。
那么得到
$$=\dfrac{1}{n}\sum\limits_{t=0}^{n-1}w_n^{-kt}F_{DFT}[t]G_{DFT}[t]$$
变为了点积。
再定义$P_{IDFT}[k]=\dfrac{1}{n}\sum\limits_{i=0}^nw_n^{-ik}F[i]$
那么有
$$P[k]=(F_{DFT}·G_{DFT})_{IDFT}[k]$$
其实就是`FFT`的算法流程,平时我们使用的`FFT`就是在计算长度为 $n=2^m$ 的循环卷积。
现在我们要解决 $n$ 为任意值的循环卷积。
首先,一个比较憨逼的想法是,先计算双倍长度的普通加法卷积,然后再把该循环的部分手动添加。
这种做法把卷积当做黑盒使用,性质很不优美。
观察任意长度$DFT$变换的式子 ($IDFT$同理)
$F_{DFT}[k]=\sum\limits_{i=0}^nw_n^{ik}F[i]$
考虑使用 $k,k-i,i$ 相关的东西凑出 $i,k$ 的乘积项以得到卷积。
- 式子1 : $\dfrac{k^2+i^2-(k-i)^2}{2}=ik\quad$ ( 除$2$可能会产生一些不愉快 )
- 式子2 : $\dbinom{i+j}{2}-\dbinom{i}{2}-\dbinom{j}{2}=\dfrac{i+j(i+j-1)-i(i-1)-j(j-1)}{2}=ij$
这里使用式子1,能得到:
$F_{DFT}[k]=\sum\limits_{i=0}^nw_n^{\frac{k^2+i^2-(k-i)^2}{2}}F[i]$
$F_{DFT}[k]=w_{2n}^{k^2}\sum\limits_{i=0}^nw_{2n}^{i^2}F[i]w_{2n}^{-(k-i)^2}$
将 $w_{2n}^{i^2}F[i]$ 与 $w_{2n}^{-(k-i)^2}$ 加法卷积即可。
这似乎称作 Bluestein 算法。
- **例题** : [POJ2821 TN's Kingdom III - Assassination](http://poj.org/problem?id=2821)
**题意** : 有三个序列 $A,B,C$ ,已知 $A*B=C$ (循环卷积),给出 $B,C$ 求 $A$.
循环卷积的“次数”是封闭的,所以我们只需要 $n$ 个“点值”即可。
循环卷积的求逆就是直接把变换而得的“点值”置为逆元(类似FWT位运算卷积的求逆)
- **进阶题** : [P5293 [HNOI2019]白兔之舞](https://www.luogu.com.cn/problem/P5293)
[[数学记录]P5293 [HNOI2019]白兔之舞](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p5293-hnoi2019-bai-tu-zhi-wu)