更新于 2026/7/10 09:17:52 作者

command_block

首先您需要知道单位根是个什么东西 : 傅里叶变换(FFT)学习笔记

先抛一个等式:

① $[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 学二项式定理

求$\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}$。

剩下的就一个快速幂了。

#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 小猪佩奇学数学

给定 $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)$的解法。

#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】复读机

应用②

• $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

  题意 : 有三个序列 $A,B,C$ ,已知 $A*B=C$ (循环卷积),给出 $B,C$ 求 $A$.

循环卷积的“次数”是封闭的,所以我们只需要 $n$ 个“点值”即可。

循环卷积的求逆就是直接把变换而得的“点值”置为逆元(类似FWT位运算卷积的求逆)

• 进阶题 : P5293 [HNOI2019]白兔之舞

  [数学记录]P5293 [HNOI2019]白兔之舞