[51nod 1258] [伯努利数] [多项式求逆] [任意模数NTT] 序列求和 V4

最新推荐文章于 2025-04-12 10:42:58 发布

LowestJN

最新推荐文章于 2025-04-12 10:42:58 发布

阅读量2.3k

点赞数

分类专栏：数论伯努利数多项式文章标签：多项式求逆 NTT 伯努利数

本文链接：https://blog.csdn.net/Coldef/article/details/72876762

版权

数论同时被 3 个专栏收录

14 篇文章

订阅专栏

多项式

7 篇文章

订阅专栏

伯努利数

2 篇文章

订阅专栏

本文介绍了如何利用多项式求逆和快速傅里叶变换(NTT)解决序列求和问题，特别是在面对非素数模的情况时，通过选择三个素数并使用中国剩余定理(CRT)进行合并，从而达到O(nlogn)的时间复杂度。文中还提及了在处理大整数时避免溢出的技巧。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

接http://blog.csdn.net/coldef/article/details/57908865

上次做一套模拟赛的时候，其中需要求自然数k次幂和，然后我只会n^2的…我记得n^2有20分，nlogn求可以爆到90分……
这里写图片描述
——鏼鏼鏼2015年国家集训队论文

大概就这样多项式求个逆，求出生成函数就可以了
这样是 $O(n\log n)$ ，但这道题模数不是满足NTT要求的素数……可以取三个NTT的素数，使得这三个素数乘积大于 $nP^2$ ，就可以用CRT合并了。

至于为什么要大于 $nP^2$ ，因为如果直接上FFT，一次FFT后每个数不会大于 $nP^2$ ，那么如果我们选了三个素数p1,p2,p3，用CRT可以求出模p1*p2*p3后的余数，因为p1*p2*p3>n*p^2，那么这样求出来后模题目要求的模数就可以了……其实原理挺简单的，但是我理解的半天……

不过直接上CRT要爆longlong，可以用一个小技巧处理

这里写图片描述
——图自AntiLeaf的博客

这样每次NTT分成三个素数的NTT，再合并，就可以了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

typedef long long ll;

const int N=300010,P=1e9+7;
const int p1=998244353,p2=1004535809,p3=469762049;

inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void rea(int &x){
    char c=nc(); x=0;
    for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline void rea(ll &x){
    char c=nc(); x=0;
    for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline ll Pow(ll x,ll y,ll p){
    x%=p; ll ret=1;
    for(;y;y>>=1,x=x*x%p) if(y&1) ret=ret*x%p;
    return ret;
}

const ll M_=1LL*p1*p2,inv1=Pow(p1,p2-2,p2),inv2=Pow(p2,p1-2,p1),inv3=Pow(M_%p3,p3-2,p3);

int rev[N],fac[N],inv[N],a[N],b[N];

struct NTT{
    int P,num;
    int w[2][N];
    void Pre(int p,int n){
        P=p; num=n;
        int ng=Pow(3,(P-1)/num,P),ig=Pow(ng,P-2,P);
        w[1][0]=w[0][0]=1;
        for(int i=1;i<num;i++)
            w[1][i]=1LL*w[1][i-1]*ng%P,w[0][i]=1LL*w[0][i-1]*ig%P;
    }
    void FFT(int *a,int n,int r){
        for(int i=1;i<n;i++) if(rev[i]>i) swap(a[i],a[rev[i]]);
        for(int i=1;i<n;i<<=1)
            for(int j=0;j<n;j+=(i<<1))
                for(int k=0;k<i;k++){
                    int x=a[j+k],y=1LL*a[j+k+i]*w[r][num/(i<<1)*k]%P;
                    a[j+k]=(x+y)%P; a[j+k+i]=(x+P-y)%P;
                }
        if(!r) for(int i=0,inv=Pow(n,P-2,P);i<n;i++) a[i]=1LL*a[i]*inv%P;
    }
}ntt[3];

inline void Pre(int n){
    fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%P;
    inv[1]=1; for(int i=2;i<=n;i++) inv[i]=1LL*(P-P/i)*inv[P%i]%P;
    inv[0]=1; for(int i=1;i<=n;i++) inv[i]=1LL*inv[i]*inv[i-1]%P;
}

inline ll mul(ll a,ll b,ll p){
  a%=p; b%=p;
  return ((a*b-(ll)((ll)((long double)a/p*b+1e-3)*p))%p+p)%p;
}

inline int CRT(int a1,int a2,int a3){
    ll A=(mul(1LL*a1*p2%M_,inv2,M_)+mul(1LL*a2*p1%M_,inv1,M_))%M_;
    ll K=(1LL*a3+p3-A%p3)*inv3%p3;
    return (K*(M_%P)+A)%P;
}

int _b[3][N],__b[N];

void Inv(int *a,int *b,int n){
    static int tmp[N];
    if(n==1) return void(b[0]=CRT(Pow(a[0],p1-2,p1),Pow(a[0],p2-2,p2),Pow(a[0],p3-2,p3)));
    Inv(a,b,n>>1);
    int L=0; while(!(n>>L&1)) L++;
    for(int i=1;i<(n<<1);i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
    for(int k=0;k<3;k++)
        for(int i=0;i<n;i++) _b[k][i]=b[i],_b[k][i+n]=0;

    for(int k=0;k<3;k++){
        for(int i=0;i<n;i++) tmp[i]=a[i],tmp[i+n]=0;
        ntt[k].FFT(tmp,n<<1,1); ntt[k].FFT(_b[k],n<<1,1);
        for(int i=0;i<(n<<1);i++) _b[k][i]=1LL*_b[k][i]*tmp[i]%ntt[k].P;
        ntt[k].FFT(_b[k],n<<1,0);
    }
    for(int i=0;i<n;i++) _b[0][i]=_b[1][i]=_b[2][i]=(P-CRT(_b[0][i],_b[1][i],_b[2][i]))%P;
    _b[0][0]=_b[1][0]=_b[2][0]=(_b[0][0]+2)%P;

    for(int k=0;k<3;k++){
        for(int i=0;i<n;i++) tmp[i]=b[i],tmp[i+n]=0;
        ntt[k].FFT(tmp,n<<1,1); ntt[k].FFT(_b[k],n<<1,1);
        for(int i=0;i<(n<<1);i++) _b[k][i]=1LL*_b[k][i]*tmp[i]%ntt[k].P;
        ntt[k].FFT(_b[k],n<<1,0);
    }
    for(int i=0;i<n;i++) b[i]=CRT(_b[0][i],_b[1][i],_b[2][i]);
}

int t,k;
ll n;

inline int C(int x,int y){
    return 1LL*fac[x]*inv[y]%P*inv[x-y]%P;
}

int main(){
    int M=1; for(;M<=50000;M<<=1);
    ntt[0].Pre(p1,M<<1);
    ntt[1].Pre(p2,M<<1);
    ntt[2].Pre(p3,M<<1);
    Pre(M);
    for(int i=0;i<M;i++) a[i]=inv[i+1];
    Inv(a,b,M);
    for(int i=0;i<M;i++) b[i]=1LL*b[i]*fac[i]%P;
    b[1]=P-b[1];
    rea(t);
    while(t--){
        rea(n); rea(k); n%=P;
        int ans=0;
        for(int i=k,prod=n;~i;prod=1LL*prod*n%P,i--)
            ans=(1LL*prod*b[i]%P*C(k+1,i)%P+ans)%P;
        ans=1LL*ans*Pow(k+1,P-2,P)%P;
        printf("%d\n",ans);
    }
    return 0;
}