2019_SCUT_三七互娱杯K_HRY and ball2(cdq分治+ntt)
题意
定义 f(n,m)为将 n个球放进 m个相同的盒子的方案数.
定义 F(n)=∑i=1nf(n,i)
输入 n, 要求输出 n行,第 i行表示 F(i)的值. 由于答案可能很大,要求输出答案模 1004535809的值
做法
显然 f(n,m)为斯特林数,把 n个球放进 i个相同盒子的生成函数为 g(x)=i!(ex−1)i
于是答案的生成函数为, h(x)=∑i=1ni!(ex−1)i=eex−1−1.
问题转化为如何求 h(x)第 i项的系数.
已知 ex−1=x+2!x2+3!x3+4!x4+...+n!xn
设 s(x)=a1x+a2x2+a3x3+a4x4+...+anxn,问题转化为已知 s(x)求 es(x)的问题.
使用待定系数法, 设 t(x)=es(x)=b0+b1x+b2x2+b3x3+b4x4+...+bnxn.
由 t′(x)=es(x)s′(x)=t(x)s′(x)得, bk=k1∑i=1kaibk−i
容易得出 b0=es(0)=1, 因此使用 cdq分治计算贡献即可求出所有的 bi.
复杂度分析: T(n)=2T(n/2)+O(nlogn), 可得 T(n)=O(nlog2n)
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1 << 18 | 7;
const int P = 1004535809, G = 3;
namespace NTT {
int w[19][2];
int power_mod(int a, int b) {
int ret = 1;
for(a %= P; b; b>>=1,a=1ll*a*a%P)
if(b&1) ret = 1ll*ret*a%P;
return ret;
}
void ntt_init() {
for(int i = 1; i < 19; i++) {
w[i][0] = power_mod(G, P-1>>i);
w[i][1] = power_mod(w[i][0], P-2);
}
}
void ntt(int *y, int len, int on) {
static int r[N], nl, ww, wn, u, v;
int i, j, k, l = __builtin_ctz(len) - 1;
if(nl != len) {
for(i = 0, nl = len; i < len; i++)
r[i] = (r[i>>1]>>1)|(i&1)<<l;
}
for(i = 0; i < len; i++)
if(i < r[i]) swap(y[i], y[r[i]]);
for(i = 1, l = 1; i < len; i <<= 1, l++)
for(j = 0, wn = w[l][on]; j < len; j+=i<<1)
for(k = j, ww = 1; k < j + i; k++, ww = 1ll*ww*wn%P)
u = y[k], v = 1ll*y[k+i]*ww%P,
y[k] = (u + v) % P, y[k+i] = (u - v + P) % P;
if(on) {
int invl = power_mod(len, P - 2);
for(i = 0; i < len; i++) y[i] = 1ll*y[i]*invl%P;
}
}
}
void conv(int *a, int *b, int l1, int l2) {
using namespace NTT;
static int i, j, l;
l = l1 + l2 - 1;
while(l&(l-1)) l += l&-l;
for(i = l1; i < l; i++) a[i] = 0;
for(i = l2; i < l; i++) b[i] = 0;
ntt(a, l, 0), ntt(b, l, 0);
for(i = 0; i < l; i++) a[i] = 1ll*a[i]*b[i]%P;
ntt(a, l, 1);
}
int ans[N], a[N], F[N], invF[N], inv[N];
void work(int l, int r) {
static int x[N], y[N];
if(l == r) return;
int mid = (l+r)>>1;
work(l, mid);
for(int i = l; i <= mid; i++) x[i-l]=ans[i];
for(int i = 0; i <= r-l; i++) y[i] = a[i];
conv(x, y, mid - l + 1, r - l + 1);
for(int i = mid + 1; i <= r; i++)
(ans[i] += 1ll*inv[i]*x[i - l]%P) %= P;
work(mid + 1, r);
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
NTT::ntt_init();
int n; scanf("%d", &n);
F[0] = invF[0] = inv[1] = 1;
for(int i = 1; i <= n; i++)F[i]=1ll*F[i-1]*i%P;
invF[n] = NTT::power_mod(F[n], P-2);
for(int i = n-1; i; i--) invF[i]=invF[i+1]*(i+1ll)%P;
for(int i = 2; i <= n; i++) inv[i] = 1ll*inv[P%i]*(P-P/i)%P;
for(int i = 1; i <= n; i++) a[i] = invF[i-1];
ans[0] = 1;
work(0, n);
for(int i = 1; i <= n; i++) printf("%d\n", 1ll*F[i]*ans[i]%P);
return 0;
}