显示代码纯文本
#include <math.h>
#include <ctime>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int MAXN=65539;
typedef long long TYPE;
typedef int type;
type mod=119<<23|1;
type god=3;
inline int input()
{
static int x;
scanf("%d",&x);
return x;
}
type pow(type a,type b,type Mod=mod)
{
type ans=1;
for(; b; b>>=1,a=(TYPE)a*a%Mod)
if(b&1)ans=(TYPE)ans*a%Mod;
return ans;
}
namespace NumberTheory {
#define print(f,g) \
{ \
printf("Printing "#f"\n"); \
for(int i=0;i<(g)-(f);++i) { \
printf("%d ",(f)[i]); \
}printf("\n"); \
}
inline void upload(type&a) {a=(a<0?a+mod:a);}
namespace Number_Lock
{
int cnt,num[64];
void Breaker(int N)
{
cnt=0;
for(int i=2; 1ll*i*i<=N; ++i)
{
if(N%i==0)
{
num[++cnt]=i;
}
while(N%i==0)N/=i;
}
if(N>1)num[++cnt]=N;
}
int getRoot(int N)
{
Breaker(N-1);
for(int j,i=2; i<N; ++i)
{
for(j=1; j<=cnt; ++j)
{
if(pow(i,(N-1)/num[j],N)==1)break;
//printf("%d\n",pow(i,(N-1)/num[j],N));
}
if(j>cnt)return i;
}
return 0;
}
}
int getLen(int L)
{
int len=1;
while(len<L)len<<=1;
return len;
}
type w_init[2][17][MAXN+10];
int FFT_init()
{
const int N=MAXN;
for(int is=0; is<2; ++is)
for(int m=2,h=1; m<=N; m<<=1,++h)
{
const int mh=m>>1;
const type wn=pow(god,is==1?(mod-1)-(mod-1)/m:(mod-1)/m);
for(int r=0; r<N; r+=m)
{
type w=1;
for(int k=0; k<mh; ++k)
{
w_init[is][h][r+k]=w;
w=(TYPE)w*wn%mod;
}
}
}
return 0;
}
void rotate(type *a,int N)
{
for(int i=1,j=0; i<N; ++i)
{
int k=N;
do j^=(k>>=1);
while(j<k);
if(i<j)std::swap(a[i],a[j]);
}
}
void FFT(type*a,int N,int is)
{
static int protect=FFT_init();
rotate(a,N);
if(is<0)is=0;
for(int m=2,h=1; m<=N; m<<=1,++h)
{
const int mh=m>>1;
for(int r=0; r<N; r+=m)
{
type*w=w_init[is][h]+r;
type*b=a+r;
type*c=a+r+mh;
for(int k=0; k<mh; ++k)
{
const type v=(TYPE)(*c)*(*w)%mod;
*c=(*b-v);upload(*c);
*b=(*b-mod+v);upload(*b);
++b;
++c;
++w;
}
}
}
if(is==0)
{
// std::reverse(a,a+N);
const type inv=pow(N,mod-2,mod);
for(int i=0; i<N; ++i)
{
a[i]=(TYPE)a[i]*inv%mod;
}
}
}
void getInv(type*a,type*b,int N)
{
if(N==1)
{
b[0]=pow(a[0],mod-2);
return ;
}
getInv(a,b,N>>1);
static type c[MAXN];
const int mh=N<<1;
memcpy(c,a,sizeof(type)*N);
memset(c+N,0,sizeof(type)*N);
FFT(c,mh,1);
FFT(b,mh,1);
for(int i=0; i<mh; ++i)
{
b[i]=(2ll-(TYPE)c[i]*b[i]%mod)*b[i]%mod;
upload(b[i]);
}
FFT(b,mh,-1);
memset(b+N,0,sizeof(type)*N);
}
void _mul_littler_(const type*_a,const int&la,const type*_b,const int&lb,type*_c)
{
static type c[MAXN];
memset(c,0,sizeof(type)*(la+lb-1));
for(int i=0; i<la; ++i)
{
for(int j=0; j<lb; ++j)
{
c[i+j]+=(TYPE)_a[i]*_b[j]%mod-mod;
c[i+j]%=mod;upload(c[i+j]);
}
}
memcpy(_c,c,sizeof(type)*(la+lb-1));
}
void _mul_greater_(const type*_a,const int&_la,const type*_b,const int&_lb,type*_c)
{
static type a[MAXN],b[MAXN];
int la=_la,lb=_lb;
while(la>1&&_a[la-1]==0)--la;
while(lb>1&&_b[lb-1]==0)--lb;
int len=getLen(la+lb);
memcpy(a,_a,sizeof(type)*la);
memset(a+la,0,sizeof(type)*(len-la));
memcpy(b,_b,sizeof(type)*lb);
memset(b+lb,0,sizeof(type)*(len-lb));
FFT(a,len,1);
FFT(b,len,1);
for(int i=0; i<len; ++i)a[i]=(TYPE)a[i]*b[i]%mod;
FFT(a,len,-1);
for(int i=0; i<la+lb-1; ++i)_c[i]=a[i];
}
const int COMPLEX=1E3;
void mulWith(const type*_a,const int&la,const type*_b,const int&lb,type*_c)
{
if(1ll*la*lb<COMPLEX)
{
_mul_littler_(_a,la,_b,lb,_c);
}
else
{
_mul_greater_(_a,la,_b,lb,_c);
}
}
void divWith(const type*_a,const int&la,const type*_b,const int&lb,type*_c)
{
static type a[MAXN],b[MAXN],c[MAXN];
int len=getLen(la),lc=la-lb+1;
memset(c,0,sizeof(type)*len<<1);
memcpy(a,_a,sizeof(type)*la);
memset(a+la,0,sizeof(type)*(len-la));
memcpy(b,_b,sizeof(type)*lb);
memset(b+lb,0,sizeof(type)*(len-lb));
std::reverse(a,a+la);
std::reverse(b,b+lb);
getInv(b,c,len);
mulWith(a,la,c,len,c);
std::reverse(c,c+lc);
for(int i=0; i<lc; ++i)_c[i]=c[i];
}
void modWith(const type*_a,const int&_la,const type*_b,const int&_lb,type*_d)
{
static type c[MAXN],lc;
int la=_la,lb=_lb;
const int len=getLen(la);
while(la>1&&_a[la-1]==0)--la;
while(lb>1&&_b[lb-1]==0)--lb;
if(lb>la)
{
for(int i=0; i<la; ++i)
_d[i]=_a[i];
return;
}
memset(c,0,sizeof(type)*la);
lc=la-lb+1;
divWith(_a,la,_b,lb,c);
while(lc>1&&c[lc-1]==0)--lc;
mulWith(_b,lb,c,lc,c);
for(int i=0; i<la; ++i)
{
c[i]=(_a[i]-c[i])%mod;
upload(c[i]);
}
lc=la;
while(lc>1&&c[lc-1]==0)--lc;
for(int i=0; i<lc; ++i)_d[i]=c[i];
}
type save[MAXN];
type answer[16][MAXN];
type filter[16][MAXN];
type w[MAXN];
void doubleDivsion(int l,int r,int dep)
{
if(l==r+1)return;
if(r==l+2)
{
save[l>>1]=answer[dep][l];
return;
}
int m=(l+r)>>1,nex=dep+1;
modWith(answer[dep]+l,r-l,filter[nex]+l,m-l,answer[nex]+l);
modWith(answer[dep]+l,r-l,filter[nex]+m,r-m,answer[nex]+m);
doubleDivsion(l,m,nex);
doubleDivsion(m,r,nex);
}
void doubleUnion(int l,int r,int dep)
{
if(r==l+1) return;
int m=((l+r)>>1),nex=dep+1;;
doubleUnion(l,m,nex);
doubleUnion(m,r,nex);
if(r==l+2)
{
if(w[l]!=-1)
{
filter[dep][l]=w[l];
filter[dep][l+1]=1;
}
else
{
filter[dep][l]=1;
filter[dep][l+1]=0;
}
}
else mulWith(filter[nex]+l,m-l,filter[nex]+m,r-m,filter[dep]+l);
}
void causeLight(type*f,int N)
{
memset(w,-1,sizeof(w));
memset(filter,0,sizeof(filter));
int len=getLen(N)<<1;
for(int i=0; i<N; ++i)w[i<<1]=f[i];
doubleUnion(0,len,0);
}
void insite(type*a,int N,type*f)
{
static type g[MAXN];
int len=getLen(N)<<1;
memset(g,0,sizeof(type)*len);
for(int i=0; i<N; ++i)g[i]=f[i];
causeLight(g,N);
modWith(a,len,filter[0],len,answer[0]);
doubleDivsion(0,len,0);
}
int runHigh(int N)
{
type ans=1;
for(int i=1; i<=N; ++i)
{
ans=1ll*ans*i%mod;
}
if(N&1)ans=1ll*ans*pow(2,mod-2,mod)%mod;
printf("%lld\n",ans);
return 0;
}
type c[MAXN],e[MAXN],B;
int Exceed(int N,int Mod)
{
B=sqrt(N);
mod=Mod;
god=Number_Lock::getRoot(mod);
for(int i=0; i<B; ++i)
{
c[i]=i+1;
}
causeLight(c,B);
memcpy(e,filter[0],sizeof(type)*B<<1);
for(int i=0; i<B; ++i)
{
c[i]=(mod-(TYPE)i*B%mod)%mod;
}
insite(e,B,c);
return 0;
}
int Fraction(int N) {
int n=N/B*B,ans=1;
for(int i=0;i<n;i+=B)
{ans=(TYPE)ans*save[i/B]%mod;}
for(int i=n+1;i<=N;++i)
{ans=(TYPE)ans*i%mod;}//printf("%d %d\n",B,ans);
return ans;
}
}
int js[MAXN],ij[MAXN];
void PreJS(const int N=MAXN-2) {
js[0]=1;
for(int i=1;i<=N;++i) {
js[i]=(TYPE)js[i-1]*i%mod;
}ij[N]=pow(js[N],mod-2,mod);
for(int i=N-1;i>=0;--i) {
ij[i]=(TYPE)ij[i+1]*(i+1)%mod;
}//printf("%d\n",js[65534]);
for(int i=1;i<=N;++i) {
js[i]=(TYPE)js[i-1]*js[i]%mod;
ij[i]=(TYPE)ij[i-1]*ij[i]%mod;
}
}
int main() {
freopen("seaHibernate.in","r",stdin);
freopen("seaHibernate.out","w",stdout);
NumberTheory::Exceed(9E8+10,input());PreJS();
int Q=input();
for(int i=1;i<=Q;++i) {
int k=input();
int n=input();
int f=NumberTheory::Fraction(n*k);
int a=(TYPE)js[n+k-1]*ij[n-1]%mod;
int b=(TYPE)js[k-1];
//printf("%d %d %d\n",f,a,b);
//fprintf(stderr,"case :%d\n",i);
printf("%lld\n",(TYPE)f*b%mod*pow(a,mod-2,mod)%mod);
}fclose(stdin);fclose(stdout);
return 0;
}
YGOI_真神名曰驴蛋蛋