NC25454. HRY and balls 2
描述
输入描述
A positive integer n.
输出描述
Output n lines, an integer per line. The integer in the m-th line represents the result of.
示例1
输入:
3
输出:
1 2 5
C++14(g++5.4) 解法, 执行用时: 662ms, 内存消耗: 7908K, 提交时间: 2019-05-09 20:23:13
#include<iostream>
#include<math.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=4e5+20,mod=1004535809;
int a[maxn],b[maxn],h[maxn];
int fac[maxn],ifac[maxn];
int n,m,k,len;
int r[maxn],inv[maxn]={1,1};
int qpow(int x,int y){
x%=mod;
int s=1;
while(y){
if(y&1)s=1ll*s*x%mod;
x=1ll*x*x%mod;y>>=1;
}
return s;
}
void NTT(int *p,int opt,int len){
for(int i=0,l=log2(len);i<len;++i){
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
if(i<r[i])swap(p[i],p[r[i]]);
}
for(int i=1;i<len;i<<=1){
int W=qpow(3,(mod-1)/(i<<1));
if(opt==-1)W=qpow(W,mod-2);
for(int j=0,s=i<<1;j<len;j+=s){
int w=1;
for(int k=0;k<i;++k,w=1ll*w*W%mod){
int X=p[j+k],Y=1ll*w*p[i+j+k]%mod;
p[j+k]=X+Y>=mod?X+Y-mod:X+Y;
p[i+j+k]=X>=Y?X-Y:X-Y+mod;
}
}
}
if(opt==-1){
int inv=qpow(len,mod-2);
for(int i=0;i<len;++i)p[i]=1ll*p[i]*inv%mod;
}
}
void Get_Mul(int *a,int *b,int *c,int len){
static int A[maxn],B[maxn];
memcpy(A,a,len<<3);memcpy(B,b,len<<3);
for(int i=len;i<len<<1;++i)A[i]=B[i]=0;
NTT(A,1,len<<1);NTT(B,1,len<<1);
for(int i=0;i<len<<1;++i)c[i]=1ll*A[i]*B[i]%mod;
NTT(c,-1,len<<1);
}
void Get_Inv(int *a,int *b,int len){
static int A[maxn];
if(len==1)return b[0]=qpow(a[0],mod-2),void();
Get_Inv(a,b,len>>1);
for(int i=0;i<len;++i)A[i]=a[i];
for(int i=len;i<(len<<1);++i)A[i]=0;
for(int i=len>>1;i<(len<<1);++i)b[i]=0;
NTT(A,1,len<<1);NTT(b,1,len<<1);
for(int i=0;i<(len<<1);++i)b[i]=(b[i]*2-1ll*A[i]*b[i]%mod*b[i]%mod+mod)%mod;
NTT(b,-1,len<<1);
}
void Get_Ln(int *a,int *b,int len){
static int A[maxn];
for(int i=0;i<len;++i)A[i]=1ll*a[i+1]*(i+1)%mod;
Get_Inv(a,b,len);Get_Mul(A,b,b,len);
if(!inv[2])for(int i=2;i<maxn;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=len-1;i;--i)b[i]=1ll*b[i-1]*inv[i]%mod;
b[0]=0;
}
void Get_Exp(int *a,int *b,int len){
static int A[maxn];
if(len==1)return b[0]=1,void();
Get_Exp(a,b,len>>1);Get_Ln(b,A,len);
for(int i=0;i<len;++i)A[i]=(1ll*a[i]-A[i]+mod)%mod;
A[0]++;Get_Mul(A,b,b,len);
}
void Get_Sqrt(int *a,int *b,int len){
static int A[maxn],B[maxn];
if(len==1)return b[0]=1,void();
Get_Sqrt(a,b,len>>1);Get_Inv(b,A,len);
for(int i=0;i<len;++i)B[i]=a[i];
Get_Mul(B,A,A,len);
if(!inv[2])for(int i=2;i<maxn;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=0;i<len;++i)b[i]=1ll*(b[i]+A[i])*inv[2]%mod;
}
void Sqrt(int *a, int *b, int len) {
static int B[maxn];
Get_Ln(a, B, len);
for(int i = 0; i < len; i++) B[i] =1ll*B[i]*inv[2]%mod;
Get_Exp(B, b, len);
}
void Get_Pow(int *a, int *b,int c, int len) {
static int B[maxn];
Get_Ln(a, B, len);
for(int i = 0; i < len; i++) B[i]=1ll*B[i]*c%mod;
Get_Exp(B, b, len);
}
void Get_Mod(int *a,int *b,int *c,int n,int m){
static int A[maxn],B[maxn],C[maxn];
int len=1;while(len<=n)len<<=1;
reverse(a,a+n+1);reverse(b,b+m+1);
memcpy(A,a,len<<3);memcpy(B,b,len<<3);
Get_Inv(B,C,len);Get_Mul(A,C,C,len);
reverse(a,a+n+1);reverse(b,b+m+1);reverse(C,C+n-m+1);
for(int i=n-m+1;i<len;++i)C[i]=0;
memcpy(A,b,len<<3); Get_Mul(A,C,C,len);
for(int i=0;i<m;++i)c[i]=(1ll*a[i]-C[i]+mod)%mod;
}
void cdq(int l,int r){
if (l==r) return;
int mid=l+r>>1;
cdq(l,mid);
for (len=1;len<=r-l;len<<=1);
for (int i=0;i<len;i++)
a[i]=b[i]=0;
for (int i=l;i<=mid;i++) a[i-l]=h[i];
for (int i=0;i<=r-l-1;i++) b[i]=ifac[i];
NTT(a,1,len);NTT(b,1,len);
for (int i=0;i<len;i++) a[i]=1ll*a[i]*b[i]%mod;
NTT(a,-1,len);
for (int i=0;i<=r-l-1;i++)
if (i+l+1>mid)
h[i+l+1]=(h[i+l+1]+1ll*a[i]*inv[i+l+1]%mod)%mod;
cdq(mid+1,r);
}
void init(){
fac[0]=1;
for (int i=1;i<maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[maxn-1]=qpow(fac[maxn-1],mod-2);
for (int i=maxn-2;i>=0;i--)
ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int main(){
init();
h[0]=1;
cin >> n;
if(!inv[2])for(int i=2;i<maxn;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
cdq(0,n);
for (int i=1;i<=n;i++)
cout << 1ll*h[i]*fac[i]%mod << '\n';
}
C++11(clang++ 3.9) 解法, 执行用时: 800ms, 内存消耗: 6124K, 提交时间: 2019-05-05 20:35:31
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int M=3e5+5;
const int N=1e5+5;
const int mod=1004535809;
int pow(int,int,int);
const int G=3,iG=pow(G,mod-2,mod);
int a[M],b[M],R[M];
void ntt(int*,int,int);
int fac[N],finv[N],inv[N];
int f[N];
void solve(int,int);
int main(){
int n;
scanf("%d",&n);
fac[0]=fac[1]=finv[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++){
fac[i]=1LL*fac[i-1]*i%mod;
inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=1;i<=n;i++) finv[i]=1LL*finv[i-1]*inv[i]%mod;
f[1]=0;
solve(1,n);
for(int i=1;i<=n;i++){
f[i]=1LL*f[i]*fac[i]%mod;
printf("%d\n",f[i]);
}
}
void solve(int s,int e){
if(s==e){
f[s]=(f[s]+finv[s-1])%mod;
f[s]=1LL*f[s]*inv[s]%mod;
return;
}
int mid=(s+e)/2;
solve(s,mid);
int len=1,L=-1,len1=e-s+1,len2=mid-s+1,tot=len1+len2-1;
while(len<tot) len<<=1,L++;
for(int i=0;i<len;i++) R[i]=(R[i>>1]>>1)|((i&1)<<L);
memset(a,0,len<<2),memset(b,0,len<<2);
for(int i=1;i<=len1;i++) a[i-1]=finv[i-1];
for(int i=s;i<=mid;i++) b[i-s]=f[i];
ntt(a,len,1),ntt(b,len,1);
for(int i=0;i<len;i++) a[i]=1LL*a[i]*b[i]%mod;
ntt(a,len,-1);
for(int i=mid+1;i<=e;i++) f[i]=(f[i]+a[i-s-1])%mod;
solve(mid+1,e);
}
void ntt(int*y,int len,int o){
for(int i=0;i<len;i++) if(i<R[i]) swap(y[i],y[R[i]]);
for(int i=1;i<len;i<<=1){
int wn=pow(o==-1?iG:G,(mod-1)/(2*i),mod);
for(int j=0;j<len;j+=2*i){
for(int k=0,w=1;k<i;k++,w=1LL*w*wn%mod){
int u=y[j+k],t=1LL*w*y[j+k+i]%mod;
y[j+k]=(u+t)%mod,y[j+k+i]=(u-t+mod)%mod;
}
}
}
if(o==-1){
for(int i=0,inv=pow(len,mod-2,mod);i<len;i++)
y[i]=1LL*y[i]*inv%mod;
}
}
int pow(int a,int p,int m){
int re=1;
for(;p;p>>=1){
if(p&1) re=1LL*re*a%m;
a=1LL*a*a%m;
}
return re;
}