显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
//阶乘转化：记f(x)=(x+block)!/x!，求n!复杂度为O(sqrt(n)log^2n)
typedef long long ll;
typedef unsigned int type;
const int N=1<<17;
int p,T;
int inc(type x,type y){x+=y;return x>=p?x-p:x;}
int dec(type x,type y){x+=p-y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
int ans=1;
for (;y;y>>=1,x=mul(x,x))
if (y&1) ans=mul(ans,x);
return ans;
}
int w[N],iw[N],inverse[N],jc[N],JC[N],pre[N],ipre[N],gen;
void init(){
inverse[1]=1;
for (int i=2;i<N;i++) inverse[i]=mul(p-p/i,inverse[p%i]);
jc[0]=JC[0]=1;
for (int i=1;i<N;i++){
jc[i]=mul(jc[i-1],i);
JC[i]=mul(JC[i-1],inverse[i]);
}
pre[0]=ipre[0]=1;
for (int i=1;i<N;i++){
pre[i]=mul(pre[i-1],jc[i]);
ipre[i]=mul(ipre[i-1],JC[i]);
}
}
int root(){
static int a[20],cnt,now=p-1;
for (int i=2;i*i<=p;i++)
if (now%i==0){
a[++cnt]=i;
while (now%i==0) now/=i;
}
if (now>1) a[++cnt]=now;
for (int i=2;i<p;i++){
bool check=1;
for (int j=1;j<=cnt;j++)
if (power(i,(p-1)/a[j])==1) check=0;
if (check) return i;
}
}
void init(int n){
w[0]=1;w[1]=power(gen,(p-1)/n);
for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
for (int i=0;i<=n;i++) iw[i]=w[n-i];
}
void fft(int n,int *a,int *w){
for (int i=0,j=0;i<n;i++){
if (i<j) swap(a[i],a[j]);
for (int k=n>>1;(j^=k)<k;k>>=1);
}
for (int i=2;i<=n;i<<=1){
int m=i>>1,step=n/i;
for (int j=0;j<n;j+=i)
for (int k=0,pos=0;k<m;k++,pos+=step){
int t=mul(a[j+k+m],w[pos]);
a[j+k+m]=dec(a[j+k],t);
a[j+k]=inc(a[j+k],t);
}
}
if (w==iw){
int del=inverse[n];
for (int i=0;i<n;i++) a[i]=mul(a[i],del);
}
}
void getinv(int n,int *a,int *b){
if (n==1) return void(b[0]=power(a[0],p-2));
getinv((n+1)>>1,a,b);
int size=1;
while (size<n+n) size<<=1;
init(size);
static int tmp[N];
for (int i=0;i<n;i++) tmp[i]=a[i];
for (int i=n;i<size;i++) tmp[i]=0;
fft(size,tmp,w);fft(size,b,w);
for (int i=0;i<size;i++) b[i]=mul(b[i],dec(2,mul(b[i],tmp[i])));
fft(size,b,iw);
for (int i=n;i<size;i++) b[i]=0;
}
void getmod(int n,int *a,int m,int *b,int *c){
static int tmp[N],inv[N];
int size=1;
while (size<n+n) size<<=1;
for (int i=0;i<size;i++) tmp[i]=inv[i]=0;
for (int i=0;i<n;i++) tmp[i]=a[n-i-1];
reverse(b,b+m);
getinv(n-m+1,b,inv);
reverse(b,b+m);
init(size);
fft(size,tmp,w);fft(size,inv,w);
for (int i=0;i<size;i++) c[i]=mul(tmp[i],inv[i]);
fft(size,c,iw);
for (int i=n-m+1;i<size;i++) c[i]=0;
reverse(c,c+n-m+1);
for (int i=0;i<m;i++) tmp[i]=b[i];
for (int i=m;i<size;i++) tmp[i]=0;
fft(size,tmp,w);fft(size,c,w);
for (int i=0;i<size;i++) c[i]=mul(tmp[i],c[i]);
fft(size,c,iw);
for (int i=0;i<size;i++) c[i]=dec(a[i],c[i]);
}
int a[N];
void geta(int *a,int l,int r){
if (l==r){a[0]=l;a[1]=1;return;}
int size=1;
while (size<=r-l+1) size<<=1;
int mid=(l+r)>>1,*L=new int[size],*R=new int[size];
for (int i=0;i<size;i++) L[i]=R[i]=0;
geta(L,l,mid);geta(R,mid+1,r);
init(size);
fft(size,L,w);fft(size,R,w);
for (int i=0;i<size;i++) a[i]=mul(L[i],R[i]);
fft(size,a,iw);
}
vector<int> k[N];
int X[N];
#define lc x<<1
#define rc x<<1|1
void build(int x,int l,int r){
if (l==r){
k[x].push_back(dec(0,X[l]));
k[x].push_back(1);
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
int size=1;
while (size<=r-l+1) size<<=1;
init(size);
static int L[N],R[N];
for (int i=0;i<k[lc].size();i++) L[i]=k[lc][i];
for (int i=k[lc].size();i<size;i++) L[i]=0;
for (int i=0;i<k[rc].size();i++) R[i]=k[rc][i];
for (int i=k[rc].size();i<size;i++) R[i]=0;
fft(size,L,w);fft(size,R,w);
for (int i=0;i<size;i++) L[i]=mul(L[i],R[i]);
fft(size,L,iw);
for (int i=0;i<=r-l+1;i++) k[x].push_back(L[i]);
}
void calc(int x,int n,int *a,int *X){
if (n==1) return void(X[0]=a[0]);
int m=n>>1;
int *tmp=new int[n*2],*mod=new int[n*2];
for (int i=0;i<n*2;i++) tmp[i]=mod[i]=0;
for (int i=0;i<k[lc].size();i++) tmp[i]=k[lc][i];
getmod(n,a,k[lc].size(),tmp,mod);
calc(lc,m,mod,X);
for (int i=0;i<n*2;i++) tmp[i]=mod[i]=0;
for (int i=0;i<k[rc].size();i++) tmp[i]=k[rc][i];
getmod(n,a,k[rc].size(),tmp,mod);
calc(rc,m,mod,X+m);
}
const int size=1<<15,block=size-1;
int factorial(int n){
int now=0,ans=1;
for (int i=1;i*block<=n;i++) ans=mul(ans,X[i-1]),now=i*block;
for (int i=now+1;i<=n;i++) ans=mul(ans,i);
return ans;
}
int main()
{
freopen("seaHibernate.in","r",stdin);
freopen("seaHibernate.out","w",stdout);
scanf("%d%d",&p,&T);
init();
gen=root();
geta(a,1,block);
for (int i=0;i<size;i++) X[i]=i*block;
build(1,0,size-1);
calc(1,size,a,X);
while (T--){
int k,n;
scanf("%d%d",&k,&n);
int ans=mul(pre[k-1],mul(ipre[n+k-1],pre[n-1]));
ans=mul(ans,factorial(n*k));
printf("%d\n",ans);
}
return 0;
}
FoolMike