单位根反演小记

· · 个人记录

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

先抛一个等式:

① [n|a]=\dfrac{1}{n}\sum\limits_{k=0}^{n-1}w_n^{ak}

证明 :

可以导出下式

应用①

例题 : 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;
}

附加练习:

应用②

循环卷积即形为 :

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,能得到:

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 算法。

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

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