zcmimi's blog
avatar
zc
2020-08-25 17:41:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
typedef long long ll;
const int N=1<<17,P=1000000007;
int pw(int x,int b,int p=P){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%p;
        b>>=1;x=1ll*x*x%p;
    }
    return res;
}
void mod(ll&x,ll p){if(x>=p)x-=p;}
ll mul(ll x,ll y,ll p){
    ll res=0;
    while(y){
        if(y&1)mod(res+=x,p);
        y>>=1;mod(x<<=1,p);
    }
    return res;
}
int fac[N],ifac[N];
int C(int n,int m){
    if(m>n)return 0;
    return 1ll*fac[n]*ifac[n-m]%P*ifac[m]%P;
}
const int G=3,Gi=332748118,
    m[3]={998244353,469762049,1004535809};
const ll M=1ll*m[0]*m[1];
int r[N],L=1;
void swap(int&x,int&y){int t=x;x=y;y=t;}
void ntt(int*A,int typ,int p){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(G,(p-1)/(len<<1),p);
        for(int i=0;i<L;i+=len<<1){
            int w=1;
            for(int k=0;k<len;++k){
                int t=1ll*A[i+k+len]*w%p;
                A[i+k+len]=(A[i+k]-t+p)%p;
                A[i+k]=(A[i+k]+t)%p;
                w=1ll*w*Wn%p;
            }
        }
    }
    if(~typ)return;
    std::reverse(A+1,A+L);
    int iL=pw(L,p-2,p);
    for(int i=0;i<L;++i)A[i]=1ll*A[i]*iL%p;
}
int crt(int x,int y,int z){
    ll a=(
        mul(1ll*x*m[1]%M,pw(m[1]%m[0],m[0]-2,m[0]),M)+
        mul(1ll*y*m[0]%M,pw(m[0]%m[1],m[1]-2,m[1]),M)
    )%M;
    ll k=((z-a)%m[2]+m[2])%m[2]*pw(M%m[2],m[2]-2,m[2])%m[2];
    return ((k%P)*(M%P)%P+a%P)%P;
}
void getL(int n){
    for(L=1;L<n;L<<=1);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
}
int ans[3][N],tmp[N];
void work(int n,int*a,int*b){
    if(n==1){
        b[0]=crt(
            pw(a[0],m[0]-2,m[0]),
            pw(a[0],m[1]-2,m[1]),
            pw(a[0],m[2]-2,m[2])
        );
        return;
    }
    work(n>>1,a,b);
    getL(n<<1);
    for(int k=0;k<3;++k)
        for(int i=0;i<n;++i)
            ans[k][i]=b[i],ans[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(tmp,1,m[k]),ntt(ans[k],1,m[k]);
        for(int i=0;i<L;++i)
            ans[k][i]=1ll*tmp[i]*ans[k][i]%m[k];
        ntt(ans[k],-1,m[k]);
    }
    for(int i=0;i<n;++i)
        ans[0][i]=ans[1][i]=ans[2][i]=
            (P-crt(ans[0][i],ans[1][i],ans[2][i]))%P;
    ans[0][0]=ans[1][0]=ans[2][0]=(ans[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(tmp,1,m[k]),ntt(ans[k],1,m[k]);
        for(int i=0;i<L;++i)
            ans[k][i]=1ll*tmp[i]*ans[k][i]%m[k];
        ntt(ans[k],-1,m[k]);
    }
    for(int i=0;i<n;++i)
        b[i]=crt(ans[0][i],ans[1][i],ans[2][i]);
}
int a[N],B[N];
void init(){
    int len=1<<16;
    fac[0]=1;
    for(int i=1;i<=len;++i)fac[i]=1ll*fac[i-1]*i%P;
    ifac[len]=pw(fac[len],P-2);
    for(int i=len;i;--i)ifac[i-1]=1ll*ifac[i]*i%P;
    for(int i=0;i<len;++i)a[i]=ifac[i+1];    
    work(len,a,B);
    for(int i=0;i<len;++i)
        B[i]=1ll*B[i]*fac[i]%P;
    B[1]=P-B[1];
}
int S(int n,int k){
    int x=0;
    for(int i=0;i<=k;++i)
        x=(x+1ll*C(k+1,i)*B[i]%P*pw(n,k+1-i)%P)%P;
    return 1ll*pw(k+1,P-2)*x%P;
}
int main(){
    init();
    int T,k;long long n;
    scanf("%d",&T);
    while(T--)
        scanf("%lld%d",&n,&k),
        printf("%lld\n",S(n%P,k));
}
51nod 1258 序列求和 V4
comment评论
Search
search