First Kind Stirling Numbers (Row)

Given the rising factorial:

[x^{\overline{n}}=\sum_{i=0}^n \begin{bmatrix}n\ i\end{bmatrix} x^i ]

To compute this using a doubling approach, observe that (x^{\overline{2n}}=x^{\overline{n}}\cdot (x+n)^{\overline{n}}). The key challenge is computing (f(x+c)) given (f(x)):

[f(x+c)=\sum_{j=0}^n \frac{x^j}{j!} \sum_{i=j}^n f_i i! \cdot \frac{c^{i-j}}{(i-j)!} ]

This reduces to a convolution problem that can be solved efficiently.

poly translate(poly f, int c) {
    poly p;
    for (int i = 0; i < f.size(); ++i) {
        f[i] = (1ll * f[i] * factorial[i]) % MOD;
        p.push_back((1ll * pow(c, i) * inv_fact[i]) % MOD);
    }
    int n = f.size();
    reverse(f.begin(), f.end());
    f = convolve(f, p);
    f.resize(n);
    reverse(f.begin(), f.end());
    for (int i = 0; i < f.size(); ++i)
        f[i] = (1ll * f[i] * inv_fact[i]) % MOD;
    return f;
}

Second Kind Stirling Numbers (Row)

Using combinatorial identities:

[m^n = \sum_{i=0}^n \binom{m}{i}\begin{Bmatrix} n \i \end{Bmatrix}i! ]

After binomial inversion:

[\begin{Bmatrix} n \m \end{Bmatrix}=\sum_{i=0}^m \frac{(-1)^i}{i!} \cdot \frac{(m-i)^n}{(m-i)!} ]

This can be computed via polynomial multiplication.

poly computeStirling2Row(int n) {
    poly a, b;
    for (int i = 0; i <= n; ++i) {
        a.push_back((1ll * pow(i, n) * inv_fact[i]) % MOD);
        b.push_back(inv_fact[i]);
        if (i & 1) b[i] = (MOD - b[i]) % MOD;
    }
    return convolve(a, b);
}

First Kind Stirling Numbers (Column)

For a single column (k=1), the generating function is:

[S_1(x)=\sum_{i=1}^\infty \frac{x^i}{i} ]

For general k, the solution is:

[k!S_k(x)=(S_1(x))^k ]

This can be copmuted using polynomial exponentiation.

poly computeStirling1Col(int n, int k) {
    poly a(n+1);
    for (int i = 1; i <= n; ++i) a[i] = inv[i];
    a = poly_pow(a, k, k);
    for (int i = 0; i <= n; ++i)
        a[i] = mul(factorial[i], mul(a[i], inv_fact[k]));
    return a;
}

Second Kind Stirling Numbers (Column)

Using exponential generating funcsions:

[G(x)=e^x-1 ]

The k-th column is then:

[\begin{Bmatrix}n\ k\end{Bmatrix}= \frac{n!}{k!}x^n^k ]

poly computeStirling2Col(int n, int k) {
    poly a(n+1);
    for (int i = 1; i <= n; ++i) a[i] = inv_fact[i];
    a = poly_pow(a, k, k);
    for (int i = 0; i <= n; ++i)
        a[i] = mul(factorial[i], mul(inv_fact[k], a[i]));
    return a;
}