Submission #45209716

---

Source Code Expand

#include<bits/stdc++.h>
#define N 1<<19
#define P 998244353
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int qpow(int k,int b){
	int ret=1;
	while(b){
		if(b&1)ret=1ll*ret*k%P;
		k=1ll*k*k%P,b>>=1;
	}
	return ret;
}
int A[N],a2[N],lnb[N];
int lim,r[N],m,k,gn,tp,inv;
int iv[N];
void init_iv(int n){
	iv[1]=1;
	for(int i=2;i<=n;i++)
		iv[i]=1ll*(P-P/i)*iv[P%i]%P;
}
void init_r(int lim){
	for(int i=0;i<lim;i++)
        r[i]=(r[i>>1]>>1)+(i&1)*(lim>>1);
}
void ntt(int *x,int opt){
	for(int i=0;i<lim;i++)
		if(r[i]<i)swap(x[i],x[r[i]]);
	for(int m=2,k=1;m<=lim;m<<=1,k<<=1){
		gn=qpow(3,(P-1)/m);
		for(int i=0;i<lim;i+=m){
			for(int j=0,g=1;j<k;j++,g=1ll*g*gn%P){
				tp=1ll*x[i+j+k]*g%P;
				x[i+j+k]=(x[i+j]-tp+P)%P;
				x[i+j]=(x[i+j]+tp)%P;
			}
		}
	}
	if(opt==-1){
		reverse(x+1,x+lim),inv=qpow(lim,P-2);
		for(int i=0;i<lim;i++)
			x[i]=1ll*x[i]*inv%P;
	}
}
void Inv(int *a,int *b,int n){
	if(n==1){
		b[0]=qpow(a[0],P-2);
		return;
	}
	Inv(a,b,(n+1)>>1);
	lim=1;while(lim<(n<<1))lim<<=1;
	init_r(lim);
	for(int i=0;i<lim;i++)A[i]=i<n?a[i]:0;
	ntt(A,1),ntt(b,1);
	for(int i=0;i<lim;i++)
		b[i]=1ll*b[i]*((2ll-1ll*A[i]*b[i]%P+P)%P)%P;
	ntt(b,-1);
	for(int i=n;i<lim;i++)b[i]=0;
}
void Ln(int *a,int *b,int n){
	for(int i=0;i<(n<<2);i++)b[i]=0;
	Inv(a,b,n);
	lim=1;while(lim<(n<<1))lim<<=1;
	init_r(lim);
	for(int i=0;i<n-1;i++)
		a2[i]=1ll*a[i+1]*(i+1)%P;
	for(int i=n-1;i<lim;i++)a2[i]=0;
	ntt(a2,1),ntt(b,1);
	for(int i=0;i<lim;i++)
		b[i]=1ll*b[i]*a2[i]%P;
	ntt(b,-1);
	for(int i=n-1;i;i--)
		b[i]=1ll*b[i-1]*iv[i]%P;
	for(int i=n;i<lim;i++)b[i]=0;
	b[0]=0;
}
void Exp(int *a,int *b,int n){
	if(n==1){
		b[0]=1;
		return;
	}
	Exp(a,b,(n+1)>>1);
	Ln(b,lnb,n);
	lim=1;while(lim<(n<<1))lim<<=1;
	init_r(lim);
	for(int i=0;i<n;i++)
		lnb[i]=(a[i]-lnb[i]+P)%P;
	for(int i=n;i<lim;i++)lnb[i]=b[i]=0;
	lnb[0]++;
	ntt(lnb,1),ntt(b,1);
	for(int i=0;i<lim;i++)
		b[i]=1ll*b[i]*lnb[i]%P;
	ntt(b,-1);
	for(int i=n;i<lim;i++)b[i]=0;
}
int n,f[N],g[N];
int main(){
	n=read(),init_iv(n);
	int fac=1;
	for(int i=1;i<=n;i++)
		f[i]=qpow(1ll*i*i%P,P-2),fac=1ll*fac*i%P;
	Exp(f,g,n+1);
	int tp=((1-2*g[n])%P+P)%P;
	printf("%d\n",(1ll*fac*fac%P*tp%P+fac)%P);
	 
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:109:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
  109 |         printf("%d\n",(1ll*fac*fac%P*tp%P+fac)%P);
      |                 ~^
      |                  |
      |                  int
      |                 %lld

Judge Result