题意

定义 $f(n,m)$f(n,m)为将 $n$n个球放进 $m$m个相同的盒子的方案数.

定义 $F\left(n\right)={\sum }_{i=1}^{n}f(n,i)$F(n)=∑i=1n​f(n,i)

输入 $n$n, 要求输出 $n$n行，第 $i$i行表示 $F\left(i\right)$F(i)的值. 由于答案可能很大，要求输出答案模 1004535809的值

做法

显然 $f(n,m)$f(n,m)为斯特林数，把 $n$n个球放进 $i$i个相同盒子的生成函数为 $g\left(x\right)=\frac{(e^x-1{)}^i}{i!}$g(x)=i!(ex−1)i​

于是答案的生成函数为, $h\left(x\right)={\sum }_{i=1}^n\frac{(e^x-1{)}^i}{i!}=e^{e^x-1}-1$h(x)=∑i=1n​i!(ex−1)i​=eex−1−1.

问题转化为如何求 $h\left(x\right)$h(x)第 $i$i项的系数.

已知 $e^x-1=x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+...+\frac{x^n}{n!}$ex−1=x+2!x2​+3!x3​+4!x4​+...+n!xn​

设 $s\left(x\right)=a_{1}x+a_2{x}^2+a_3{x}^3+a_4{x}^4+...+a_n{x}^n$s(x)=a1​x+a2​x2+a3​x3+a4​x4+...+an​xn，问题转化为已知 $s\left(x\right)$s(x)求 $e^{s\left(x\right)}$es(x)的问题.

使用待定系数法, 设 $t\left(x\right)=e^{s\left(x\right)}=b_0+b_{1}x+b_2{x}^2+b_3{x}^3+b_4{x}^4+...+b_n{x}^n$t(x)=es(x)=b0​+b1​x+b2​x2+b3​x3+b4​x4+...+bn​xn.
由 $t^{\prime }\left(x\right)=e^{s\left(x\right)}{s}^{\prime }\left(x\right)=t\left(x\right)s^{\prime }\left(x\right)$t′(x)=es(x)s′(x)=t(x)s′(x)得, $b_k=\frac{1}{k}{\sum }_{i=1}^k{a}_i{b}_{k-i}$bk​=k1​∑i=1k​ai​bk−i​

容易得出 $b_0=e^{s\left(0\right)}=1$b0​=es(0)=1, 因此使用 $cdq$cdq分治计算贡献即可求出所有的 $b_i$bi​.

复杂度分析: $T\left(n\right)=2T\left(n/2\right)+O\left(nlogn\right)$T(n)=2T(n/2)+O(nlogn), 可得 $T\left(n\right)=O\left(nlo{g}^{2}n\right)$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;
}