单位根性质

单位根一个神奇的性质：

$$ {1\over k}\sum_{i=0}^{k-1}\omega_{k}^{ni}=[k\mid n] $$

证明：

• 当 $k\mid n$ 时：

  $$ {1\over k}\sum_{i=0}^{k-1}\omega_{k}^{ni}={1\over k}\sum_{i=0}^{k-1}\omega_{k}^0=1 $$

• 当 $k\not\mid n$ 时：

  $$ {1\over k}\sum_{i=0}^{k-1}\omega_{k}^{ni}={1\over k}\cdot{\omega_{k}^{0}(1-\omega_{k}^{nk})\over 1-\omega_{k}^{n}}=0 $$

单位根反演

用这个可以求出生成函数 $k$ 的倍数位置上的系数的和：

$$ f(x)=\sum_{i}a_ix^i\\ \sum_{k\mid i}a_i=\sum_{i}a_i[k\mid i]={1\over k}\sum_{i}a_i\sum_{j=0}^{k-1}\omega_{k}^{ij}={1\over k}\sum_{j=0}^{k-1}\sum_{i}a_i(\omega_{k}^{j})^i={1\over k}\sum_{j=0}^{k-1}f(\omega_{k}^{j}) $$

扩展

如果要求 $\sum_{i}a_i[i\bmod k=r]$ 咋办？

其实只需要把 $f(x)$ 向左移动 $r$ 个就行了：$f(x)\over x^r$ 。

$$ \sum_{i}a_i[i\bmod k=r]={1\over k}\sum_{j=0}^{k-1}{f(\omega_{k}^{j})\over\omega_{k}^{jr}} $$

例题

LOJ6485 LJJ 学二项式定理

转化为求：

$$ \sum_{k=0}^{3}a_k\sum_{i=0}^{n}{n\choose i}s^i[k\mid i] $$

我们把 ${n\choose i}s^i$ 看成系数，构造 $f(x)=\sum_{i=0}^{n}{n\choose i}s^ix^i=(sx+1)^n$ ，那么：

$$ \sum_{r=0}^{3}a_r\sum_{i=0}^{n}{n\choose i}s^i[i\bmod 4=r]={1\over 4}\sum_{r=0}^{3}a_r\sum_{j=0}^{3}{f(\omega_{4}^{j})\over\omega_{4}^{jr}} $$

由于是在模意义下，同NTT一样，我们把单位根改成原根就行了。

#include<cstdio>
using namespace std;
typedef long long LL;
const int MOD=998244353,inv4=748683265;

int te,S,a[4],w[4],inv[4],ans;LL n;

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,LL b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;}
int main(){
    w[0]=1;w[1]=Pow(3,(MOD-1)/4);w[2]=MUL(w[1],w[1]);w[3]=MUL(w[2],w[1]);
    for (int i=0;i<4;i++) inv[i]=Pow(w[i],MOD-2);
    for (scanf("%d",&te);te;te--){
        scanf("%lld%d",&n,&S);for (int i=0;i<4;i++) scanf("%d",&a[i]);
        ans=0;
        for (int i=0;i<4;i++){
            int F=0;for (int j=0;j<4;j++) F=ADD(F,MUL(Pow(MUL(S,w[j])+1,n),inv[i*j%4]));
            ans=ADD(ans,MUL(a[i],MUL(F,inv4)));
        }
        printf("%d\n",ans);
    }
    return 0;
}