Submit Info #36953

Problem Lang User Status Time Memory
Stirling Number of the First Kind cpp-acl Gwj AC 1362 ms 23.14 MiB

ケース詳細
Name Status Time Memory
0_00 AC 7 ms 4.42 MiB
1_00 AC 7 ms 4.46 MiB
262143_00 AC 650 ms 12.45 MiB
262144_00 AC 1333 ms 20.75 MiB
2_00 AC 7 ms 4.42 MiB
491519_00 AC 1362 ms 21.32 MiB
499999_00 AC 1361 ms 19.38 MiB
500000_00 AC 1351 ms 23.14 MiB
5000_00 AC 23 ms 4.74 MiB
example_00 AC 6 ms 4.48 MiB

/* { ###################### # Author # # Gary # # 2021 # ###################### */ #include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define check_min(a,b) a=min(a,b) #define check_max(a,b) a=max(a,b) using namespace std; //inline int read(){ // int x=0; // char ch=getchar(); // while(ch<'0'||ch>'9'){ // ch=getchar(); // } // while(ch>='0'&&ch<='9'){ // x=(x<<1)+(x<<3)+(ch^48); // ch=getchar(); // } // return x; //} const int INF=0x3f3f3f3f; typedef pair<int,int> mp; /*} */ struct NTT{ int MOD; int g; int len; int rev[1<<20]; NTT(int M,int G){ MOD=M,g=G; } void butterfly(vector<int> & v){ rep(i,len){ rev[i]=rev[i>>1]>>1; if(i&1) rev[i]|=len>>1; } rep(i,len) if(rev[i]>i) swap(v[i],v[rev[i]]); } LL quick(LL A,LL B){ if(B==0) return 1; LL tmp=quick(A,B>>1); tmp*=tmp; tmp%=MOD; if(B&1) tmp*=A,tmp%=MOD; return tmp; } int inv(int x){ return quick(x,MOD-2); } vector<int> ntt(vector<int> v,int ty){ for(auto & it: v){ it%=MOD; } butterfly(v); vector<int> nex; for(int l=2;l<=len;l<<=1){ nex.clear(); nex.resize(len); int step=quick(g,(MOD-1)/l); if(ty==-1) step=inv(step); for(int j=0;j<len;j+=l){ int now=1; for(int k=0;k<l/2;++k){ int A,B; A=v[j+k]; B=v[j+l/2+k]; B=1ll*now*B%MOD; nex[j+k]=(A+B)%MOD; nex[j+k+l/2]=(A-B+MOD)%MOD; now=1ll*now*step%MOD; } } v=nex; } return v; } void getlen(int x){ len=1; while(len<x){ len<<=1; } } vector<int> mul(vector<int> A,vector<int> B){ getlen(A.size()+B.size()); A.resize(len); B.resize(len); A=ntt(A,1); B=ntt(B,1); rep(i,len) A[i]=1ll*A[i]*B[i]%MOD; A=ntt(A,-1); int iv=inv(len); rep(i,len){ A[i]=1ll*A[i]*iv%MOD; } while(!A.empty()&&A.back()==0) A.pop_back(); return A; } }ntt(998244353,3); const int MOD=998244353; int fact[500000+20],ifact[500000+20]; vector<int> calc(int n){ if(n==0) return vector<int> (1,1); if(n&1){ vector<int> tmp=calc(n-1); vector<int> ret(n+1,0); rb(i,0,n-1) ret[i+1]=tmp[i],ret[i]-=1ll*tmp[i]*(n-1)%MOD; rb(i,0,n){ if(ret[i]<0) ret[i]+=MOD;} return ret; } n>>=1; vector<int> tmp=calc(n); vector<int> ttmp(n+1); int k=MOD-n; int z=1; rb(i,0,n){ ttmp[n-i]=1ll*z*ifact[i]%MOD; z=1ll*z*k%MOD; } vector<int> x=tmp; rb(i,0,n){ x[i]=1ll*x[i]*fact[i]%MOD; } x=ntt.mul(x,ttmp); x.resize(n+n+1); vector<int> oth(n+1); rb(i,0,n) oth[i]=1ll*ifact[i]*x[i+n]%MOD; oth=ntt.mul(oth,tmp); oth.resize(n+n+1); return oth; } int main(){ fact[0]=1; rb(i,1,500000){ fact[i]=1ll*fact[i-1]*i%MOD; } ifact[500000]=ntt.quick(fact[500000],MOD-2); rl(i,500000-1,0) ifact[i]=1ll*(i+1)*ifact[i+1]%MOD; int n; scanf("%d",&n); vector<int> tmp=calc(n); rb(i,0,n) printf("%d ",tmp[i]); return 0; }