∑MathAdvanced

Stirling Numbers of First Kind

Key Points

•
Stirling numbers of the first kind count permutations by their number of cycles and connect power polynomials to rising/falling factorials.
•
There are two sign conventions: unsigned cycle numbers ${n $[]$ k}$ and signed numbers $s(n,k)=(-1)^{n-k}{n $[]$ k}$.
•
They satisfy the key recurrence ${n $[]$ k}=(n-1){n-1 $[]$ k}+{n-1 $[]$ k-1}$, mirroring how element n is inserted into a permutation.
•
The polynomial identity $x^{ $\overline{n}$ }=x(x+1) $\dots$ (x+n-1)= $\sum_{k = 0}^{n}$ {n $[]$ k} $x^{k}$ $ packages a whole row of Stirling numbers as coefficients.
•
Conversely, the falling factorial expansion $x^{ $\underline{n}$ }= $\sum_{k = 0}^{n}$ s(n,k) $x^{k}$ $ uses the signed numbers.
•
They enable fast conversion between power basis and factorial bases, which is vital in combinatorics and algorithmic polynomial transforms.
•
Dynamic programming computes a triangle up to N in O( $N^{2}$ ) time; NTT-based product trees can compute a whole row in roughly O(N lo $g^{2}$ N).
•
In programming contests, these numbers are typically computed modulo a prime (e.g., 998244353) to avoid overflow.

Prerequisites

→Permutations and cycle decomposition — Stirling numbers of the first kind count permutations by their number of cycles, so understanding cycle structure is fundamental.
→Factorials and binomial coefficients — Many identities and checks (like evaluating at x=1 or relating to n!) rely on factorial arithmetic.
→Polynomial representations and bases — The main applications involve converting between power and factorial bases of polynomials.
→Dynamic programming on triangular recurrences — The standard way to compute a table of Stirling numbers uses a DP recurrence akin to Pascal’s triangle.
→Modular arithmetic — Values quickly overflow; computations are routinely done modulo a prime such as 998244353.
→Fast polynomial multiplication (FFT/NTT) — Efficiently computing a full row {n \brack k} for large n uses polynomial products accelerated by NTT.
→Divide-and-conquer algorithms — Product trees recursively multiply many linear factors to build the rising factorial polynomial.
→Linear algebra (triangular systems) — Basis conversion from power to falling factorial is an upper-triangular solve using s(n,k).

Detailed Explanation

Tap terms for definitions

01Overview

Stirling numbers of the first kind are combinatorial numbers that count how many permutations of n elements have exactly k cycles. They come in two closely related flavors: the unsigned cycle numbers, often written as {n \brack k}, and the signed numbers s(n,k), which alternate in sign and satisfy s(n,k) = (-1)^{n-k}{n \brack k}. Beyond counting, they serve as a bridge between the standard power basis of polynomials (1, x, x^2, ...) and the factorial bases: the rising factorial x^{\overline{n}} = x(x+1)...(x+n-1) and the falling factorial x^{\underline{n}} = x(x-1)...(x-n+1). In fact, the coefficients of these factorial polynomials are Stirling numbers of the first kind. Algorithmically, these numbers can be generated efficiently using a simple recurrence that reflects how permutations gain cycles when a new element is inserted. The same recurrence creates a Pascal-like triangular table. For high-performance tasks (like handling a single large n with many queries over k), one can use polynomial multiplication and number-theoretic transforms (NTT) because the nth rising factorial expands to a polynomial whose coefficients are the unsigned Stirling numbers of the first kind. These properties make Stirling numbers a staple tool in competitive programming for tasks involving permutations, polynomial transformations, and combinatorial identities.

02Intuition & Analogies

Imagine you are seating n people around several round tables, where seat rotations are considered the same. Such a seating at round tables corresponds to decomposing a permutation into cycles: each table is a cycle, and the people in that cycle rotate among themselves. If you seat everyone so that there are exactly k tables (cycles), then each such arrangement is counted by the unsigned Stirling number {n \brack k}. When you add a new person n, you have two choices: either start a new table for them (which increases the cycle count by one) or insert them into an existing table, which keeps the cycle count the same but multiplies options by the number of positions available on that table. This simple story explains the classic recurrence and why a factor (n-1) appears: there are (n-1) places to insert the new person into the cycle structure of a permutation of n-1 elements without creating a new cycle. For polynomials, think of the rising factorial x(x+1)(x+2)... — it is like a machine that multiplies by a new linear factor each time you "add a person." Each multiplication slightly changes the coefficients, just as adding a person changes the cycle structure. The coefficients that emerge after all n multiplications are exactly the counts of permutations with different numbers of cycles. In this way, Stirling numbers are the bookkeeping layer that tracks how the structure evolves when you build up permutations or polynomials step by step.

03Formal Definition

Let

S_{n}

be the set of all permutations of {1,2,...,n}. Every permutation decomposes uniquely into disjoint cycles. The unsigned Stirling number of the first kind, denoted {n

[]

k}, is defined as the number of permutations in

S_{n}

that have exactly k cycles. The signed Stirling number of the first kind is defined by s(n,k) = (-1)^{n-k}{n

[]

k}. These numbers satisfy boundary conditions {0

[]

0} = 1, {n

[]

0} = 0 for

n > 0

, and the recurrence {n

[]

k} = (n-1){n-1

[]

k} + {n-1

[]

k-1} for n,k

\geq

1. Equivalently, the signed version obeys s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k). They also characterize changes of basis between powers and factorials. The rising factorial expands as x^{

\overline{n}

} =

\sum_{k = 0}^{n}

[]

x^{k}

, while the falling factorial expands as x^{

\underline{n}

} =

\sum_{k = 0}^{n}

s(n,k)

x^{k}

. Consequently, if a polynomial is expressed in the falling factorial basis, converting to the power basis uses s(n,k), and the inverse conversion can be done via triangular solving or with Stirling numbers of the second kind. Column-wise exponential generating functions are given by \(

\sum_{n \geq k}

[]

\frac{x ^{n}}{n !}

\frac{( - l n ( 1 - x ) ) ^{k}}{k !}

\), tying them to cycle structures in permutations.

04When to Use

Use Stirling numbers of the first kind when problems involve permutations classified by their number of cycles, e.g., counting permutations with exactly k cycles or analyzing random permutations’ cycle counts. They are also essential when switching between polynomial representations: from the standard power basis to rising/falling factorial bases or vice versa. This appears in tasks like evaluating sums with terms like (\binom{x}{n} n!), performing finite difference methods, manipulating Newton series, and converting between coefficient formats in combinatorial generating functions. In algorithmic settings, pick the DP triangle for many small-to-medium values (n up to a few thousands) and multiple queries. For a single large n (e.g., n up to 2e5) with queries over many k, compute the entire row as coefficients of the rising factorial polynomial using divide-and-conquer convolution with NTT. For basis conversions of polynomials with degree D (e.g., converting to or from falling factorial basis), a precomputed triangular table of s(n,k) enables O(D^2) transforms, which are often fast enough; if D is very large, consider FFT/NTT-based divide-and-conquer transforms.

⚠️Common Mistakes

• Mixing sign conventions: Many texts use s(n,k) for the signed numbers and {n \brack k} for the unsigned ones. Forgetting the factor (-1)^{n-k} leads to wrong signs in expansions. Always check whether the problem is using signed or unsigned definitions. • Off-by-one in recurrences: The factor in the recurrence is (n-1), not n. The correct relations are {n \brack k} = (n-1){n-1 \brack k} + {n-1 \brack k-1} and s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k). Also ensure base cases {0 \brack 0} = 1 and zeros elsewhere for k<0 or k>n. • Overflow in exact arithmetic: Values grow super-exponentially; using 64-bit integers without modular arithmetic overflows quickly (beyond n≈25). In contests, compute modulo a prime (e.g., 998244353) or use big integers for small n. • Confusing rising vs. falling factorial identities: Unsigned numbers expand rising factorials, signed numbers expand falling factorials. Mixing them gives incorrect coefficients in polynomial conversions. • Triangular transforms direction: To convert from power basis to falling factorial basis using s(n,k), you must solve an upper-triangular system (process degrees from high to low). A straight sum with s(n,k) gives the opposite direction (falling → power). • NTT pitfalls: Wrong convolution size (not a power of two), missing bit-reversal, or using a modulus without a suitable primitive root breaks the result. Test small cases and keep normalization/modulo steps consistent.

Key Formulas

Unsigned Recurrence

[k n] = (n - 1) [k n - 1] + [k - 1 n - 1]

Explanation: Either insert the nth element into an existing cycle (keeping k cycles, with n−1 positions) or start a new 1-cycle (increasing cycles to k). This recurrence builds the Pascal-like triangle for unsigned Stirling numbers.

Signed Recurrence

s (n, k) = s (n - 1, k - 1) - (n - 1) s (n - 1, k)

Explanation: The signed version mirrors the same combinatorics but accounts for sign changes. It is equivalent to the unsigned recurrence via s(n,k)=(-1)^{n-k}{n $[]$ k}.

Sign Relation

s (n, k) = (- 1)^{n - k} [k n]

Explanation: The signed and unsigned variants differ by a factor of (−1)^{n−k}. This identity lets you freely convert between the two conventions.

Rising Factorial Expansion

x^{\overline{n}} = x (x + 1) \dots (x + n - 1) = k = 0 \sum n [k n] x^{k}

Explanation: The coefficients of the nth rising factorial are the unsigned Stirling numbers. Computing this product yields an entire row {n $[]$ k} as polynomial coefficients.

Falling Factorial Expansion

x^{\underline{n}} = x (x - 1) \dots (x - n + 1) = k = 0 \sum n s (n, k) x^{k}

Explanation: The coefficients of the nth falling factorial are the signed Stirling numbers. This provides a direct way to convert from falling factorial basis to power basis.

Column EGF (Unsigned)

n \geq k \sum [k n] \frac{x ^{n}}{n !} = \frac{( - ln ( 1 - x ) ) ^{k}}{k !}

Explanation: Fixing k, the exponential generating function over n involves powers of −ln(1−x). This reflects the cycle structure decomposition in permutations.

Inverse via Stirling Second Kind

x^{n} = k = 0 \sum n S (n, k) x^{\underline{k}}

Explanation: Powers can be expressed in the falling factorial basis using Stirling numbers of the second kind. This identity shows that the two Stirling families are inverse transforms.

Falling-to-Power Coefficients

a_{k} = n = k \sum d b_{n} s (n, k) (0 \leq k \leq d)

Explanation: If a polynomial is p(x)= $\sum$ $b_{n}$ x^{ $\underline{n}$ }, then its power coefficients $a_{k}$ are obtained by a triangular sum with s(n,k). This is a direct evaluation of the falling factorial expansion.

Power-to-Falling Back-Substitution

b_{n} = a_{n} - t = n + 1 \sum d b_{t} s (t, n)

Explanation: To recover falling factorial coefficients $b_{n}$ from power coefficients $a_{k}$ , solve the upper-triangular system induced by s(t,n). Since s(n,n)=1, process degrees from high to low.

DP Complexity

T_{DP} (N) = O (N^{2}), S_{DP} (N) = O (N^{2}) or O (N)

Explanation: Building the triangle up to N takes quadratic time. Space can be quadratic to store all values or linear if only the last row is needed.

NTT Product-Tree Complexity

T_{NTT} (n) = O (n lo g^{2} n), S_{NTT} (n) = O (n)

Explanation: Computing the polynomial x^{ $\overline{n}$ } as a product of n linear factors via divide-and-conquer and NTT yields near-linearithmic time in n with linear space.

Complexity Analysis

Dynamic programming via the recurrence builds a triangular table of size about N(N+1)/2. Time is O(

N^{2}

) because each cell {n

[]

k} (or s(n,k)) depends on two previously computed cells. If you only need a single row for a specific n, you can maintain one or two rows, reducing space to O(N). If you need many rows (e.g., to answer multiple queries for various n and k), storing the full table costs O(

N^{2}

) space. Arithmetic is usually done modulo a prime to avoid overflow; otherwise, big integers are required and bit-complexity becomes relevant. When n is large and you need the entire row {n

[]

0..n}, computing x^{

\overline{n}

} = ∏_{

i=0}^{n-1}(x+i

) as a polynomial is more efficient using a divide-and-conquer product tree with NTT-based convolutions. Each level multiplies polynomials whose total degree sums to n, and there are O(log n) levels; each convolution on size m costs O(m log m) time. Aggregating across levels yields O(n lo

g^{2}

n) time and O(n) auxiliary space. This method is superior to O(

n^{2}

) DP for very large n when fast polynomial multiplication is available. For basis conversions of a degree-d polynomial using precomputed s(n,k), the direct triangular transforms cost O(

d^{2}

) time and O(

d^{2}

) space to store the table. If you do only a few conversions with large d, you can compute rows of s(n,k) on the fly in O(d) per new n using the recurrence, or use divide-and-conquer transforms with FFT/NTT to reduce asymptotic cost, though with higher constants and implementation complexity.

Code Examples

DP: Build signed and unsigned Stirling numbers of the first kind (mod prime)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute unsigned {n\brack k} and signed s(n,k) modulo MOD up to N
5 // Recurrence (unsigned): {n\brack k} = (n-1){n-1\brack k} + {n-1\brack k-1}
6 // Signed relation: s(n,k) = (-1)^{n-k} {n\brack k}
7 
8 static const int MOD = 998244353; // NTT-friendly prime; works well for modular computations
9 
10 int addmod(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
11 int submod(int a, int b){ a -= b; if(a < 0) a += MOD; return a; }
12 int mulmod(long long a, long long b){ return int((a * b) % MOD); }
13 
14 int modpow(long long a, long long e){ long long r=1%MOD; a%=MOD; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; } return (int)r; }
15 
16 int main(){
17     ios::sync_with_stdio(false);
18     cin.tie(nullptr);
19 
20     int N = 10; // build up to N; adjust as needed
21 
22     vector<vector<int>> s1u(N+1, vector<int>(N+1, 0)); // unsigned {n\brack k}
23     s1u[0][0] = 1;
24     for(int n=1; n<=N; ++n){
25         for(int k=1; k<=n; ++k){
26             int term1 = mulmod(n-1, s1u[n-1][k]);
27             int term2 = s1u[n-1][k-1];
28             s1u[n][k] = addmod(term1, term2);
29         }
30     }
31 
32     // Build signed table via sign relation: s(n,k) = (-1)^{n-k} {n\brack k}
33     vector<vector<int>> s1s(N+1, vector<int>(N+1, 0)); // signed s(n,k)
34     for(int n=0; n<=N; ++n){
35         for(int k=0; k<=n; ++k){
36             int sign = ((n - k) % 2 == 0) ? 1 : MOD-1; // (-1)^{n-k} mod MOD
37             s1s[n][k] = mulmod(sign, s1u[n][k]);
38         }
39     }
40 
41     // Demonstration: print small values
42     cout << "Unsigned Stirling numbers of the first kind {n\\brack k} up to N=" << N << "\n";
43     for(int n=0; n<=N; ++n){
44         for(int k=0; k<=n; ++k){
45             cout << s1u[n][k] << (k==n?'\n':' ');
46         }
47     }
48     cout << "\nSigned Stirling numbers of the first kind s(n,k) up to N=" << N << "\n";
49     for(int n=0; n<=N; ++n){
50         for(int k=0; k<=n; ++k){
51             cout << s1s[n][k] << (k==n?'\n':' ');
52         }
53     }
54 
55     // Example query: number of permutations of n=7 with k=3 cycles
56     int n=7, k=3;
57     cout << "{" << n << "\\brack" << k << "} mod MOD = " << s1u[n][k] << "\n";
58     return 0;
59 }
60

This program builds the Pascal-like triangle for unsigned Stirling numbers {n \brack k} using the classic recurrence, then derives the signed table via s(n,k) = (-1)^{n-k}{n \brack k}. All computations are done modulo 998244353 to avoid overflow. It prints both tables up to N and answers a sample query.

Time: O(N^2)Space: O(N^2)

Polynomial basis conversion: power basis ⇄ falling factorial basis via s(n,k)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 static const int MOD = 998244353;
5 int addmod(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
6 int submod(int a, int b){ a-=b; if(a<0) a+=MOD; return a; }
7 int mulmod(long long a, long long b){ return int((a*b)%MOD); }
8 
9 // Precompute signed Stirling numbers of the first kind s(n,k) up to D
10 vector<vector<int>> signed_stirling1(int D){
11     vector<vector<int>> s(D+1, vector<int>(D+1, 0));
12     s[0][0] = 1;
13     for(int n=1; n<=D; ++n){
14         for(int k=1; k<=n; ++k){
15             // s(n,k) = s(n-1,k-1) - (n-1) s(n-1,k)
16             int term1 = s[n-1][k-1];
17             int term2 = mulmod(n-1, s[n-1][k]);
18             s[n][k] = submod(term1, term2);
19         }
20     }
21     return s;
22 }
23 
24 // Given p(x) = sum_{k=0}^d a_k x^k, compute b such that p(x) = sum_{n=0}^d b_n x^{\underline{n}}
25 // Using the relation: a_k = sum_{n=k}^d b_n s(n,k) (upper-triangular system)
26 vector<int> power_to_falling(const vector<int>& a, const vector<vector<int>>& s){
27     int d = (int)a.size() - 1;
28     vector<int> b(d+1, 0);
29     // Back substitution from high degree down to 0; s(n,n) = 1
30     for(int n=d; n>=0; --n){
31         int rhs = a[n];
32         for(int t=n+1; t<=d; ++t){
33             // subtract known contributions b_t * s(t,n)
34             rhs = submod(rhs, mulmod(b[t], s[t][n]));
35         }
36         b[n] = rhs; // since s(n,n) = 1
37     }
38     return b;
39 }
40 
41 // Given b for q(x) = sum_{n=0}^d b_n x^{\underline{n}}, compute a for power basis q(x) = sum a_k x^k
42 // Using direct triangular sum: a_k = sum_{n=k}^d b_n s(n,k)
43 vector<int> falling_to_power(const vector<int>& b, const vector<vector<int>>& s){
44     int d = (int)b.size() - 1;
45     vector<int> a(d+1, 0);
46     for(int n=0; n<=d; ++n){
47         for(int k=0; k<=n; ++k){
48             a[k] = addmod(a[k], mulmod(b[n], s[n][k]));
49         }
50     }
51     return a;
52 }
53 
54 int main(){
55     ios::sync_with_stdio(false);
56     cin.tie(nullptr);
57 
58     // Example polynomial: p(x) = 2 + 3x + 5x^2 + 7x^3
59     vector<int> a = {2,3,5,7};
60     int d = (int)a.size() - 1;
61 
62     // Precompute signed Stirling numbers up to degree d
63     auto s = signed_stirling1(d);
64 
65     // Convert to falling factorial basis
66     vector<int> b = power_to_falling(a, s);
67 
68     // Convert back to power basis to verify round-trip
69     vector<int> a2 = falling_to_power(b, s);
70 
71     // Output
72     cout << "Coefficients a_k in power basis:" << '\n';
73     for(int i=0;i<=d;++i) cout << a[i] << (i==d?'\n':' ');
74     cout << "Coefficients b_n in falling factorial basis:" << '\n';
75     for(int i=0;i<=d;++i) cout << b[i] << (i==d?'\n':' ');
76     cout << "Back to power basis (should match a):" << '\n';
77     for(int i=0;i<=d;++i) cout << a2[i] << (i==d?'\n':' ');
78 
79     return 0;
80 }
81

This code precomputes signed Stirling numbers s(n,k) via their recurrence and uses them to convert between the power basis and the falling factorial basis. The conversion from power to falling solves an upper-triangular system by back-substitution, while the conversion from falling to power is a direct triangular sum.

Time: O(d^2)Space: O(d^2)

Fast row computation: compute all {n\brack k} as coefficients of x(x+1)...(x+n−1) via NTT

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // NTT implementation for modulus 998244353 (primitive root = 3)
5 static const int MOD = 998244353;
6 static const int G = 3;
7 
8 int addmod(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
9 int submod(int a, int b){ a-=b; if(a<0) a+=MOD; return a; }
10 int mulmod(long long a, long long b){ return int((a*b)%MOD); }
11 int modpow(long long a, long long e){ long long r=1%MOD; a%=MOD; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; } return (int)r; }
12 
13 void ntt(vector<int>& a, bool invert){
14     int n = (int)a.size();
15     static vector<int> rev;
16     static vector<int> roots{0,1};
17     if ((int)rev.size() != n){
18         int k = __builtin_ctz(n);
19         rev.assign(n,0);
20         for(int i=0;i<n;++i){ rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1)); }
21     }
22     if ((int)roots.size() < n){
23         int k = __builtin_ctz(roots.size());
24         roots.resize(n);
25         while ((1<<k) < n){
26             int z = modpow(G, (MOD-1)>>(k+1));
27             for(int i=1<<(k-1); i<(1<<k); ++i){
28                 roots[2*i] = roots[i];
29                 roots[2*i+1] = mulmod(roots[i], z);
30             }
31             ++k;
32         }
33     }
34     for(int i=0;i<n;++i){ if(i<rev[i]) swap(a[i], a[rev[i]]); }
35     for(int len=1; len<n; len<<=1){
36         for(int i=0; i<n; i+=2*len){
37             for(int j=0; j<len; ++j){
38                 int u = a[i+j];
39                 int v = mulmod(a[i+j+len], roots[len+j]);
40                 a[i+j] = addmod(u, v);
41                 a[i+j+len] = submod(u, v);
42             }
43         }
44     }
45     if(invert){
46         reverse(a.begin()+1, a.end());
47         int inv_n = modpow(n, MOD-2);
48         for(int &x: a) x = mulmod(x, inv_n);
49     }
50 }
51 
52 vector<int> multiply(vector<int> a, vector<int> b){
53     int need = (int)a.size() + (int)b.size() - 1;
54     int n=1; while(n<need) n<<=1;
55     a.resize(n); b.resize(n);
56     ntt(a,false); ntt(b,false);
57     for(int i=0;i<n;++i) a[i] = mulmod(a[i], b[i]);
58     ntt(a,true);
59     a.resize(need);
60     return a;
61 }
62 
63 // Build polynomial P(x) = prod_{i=L}^{R-1} (x + i) via divide-and-conquer
64 vector<int> build_product(int L, int R){
65     if(R - L == 1){
66         // (x + L) => coefficients [L, 1]
67         return vector<int>{ (L%MOD + MOD)%MOD, 1 };
68     }
69     int M = (L + R) >> 1;
70     auto left = build_product(L, M);
71     auto right = build_product(M, R);
72     return multiply(left, right);
73 }
74 
75 // Compute the unsigned Stirling numbers of the first kind for a fixed n as a vector of size n+1
76 // They are exactly the coefficients of x(x+1)...(x+n-1)
77 vector<int> stirling1_unsigned_row_fast(int n){
78     if(n==0) return vector<int>{1};
79     auto P = build_product(0, n); // product (x + 0)(x + 1)...(x + n-1)
80     // Note: factor (x+0) = x ensures degree n and zero constant term
81     // P[k] is coefficient of x^k; equals {n\brack k}
82     // Ensure size n+1
83     if((int)P.size() < n+1) P.resize(n+1, 0);
84     return P;
85 }
86 
87 int main(){
88     ios::sync_with_stdio(false);
89     cin.tie(nullptr);
90 
91     int n = 8;
92     auto row = stirling1_unsigned_row_fast(n);
93 
94     cout << "Unsigned Stirling numbers of the first kind for n=" << n << "\n";
95     for(int k=0;k<=n;++k){
96         cout << "{" << n << "\\brack" << k << "} = " << row[k] << "\n";
97     }
98 
99     // Sanity check: coefficient sum at x=1 equals n! (since 1^{\overline{n}} = n!)
100     long long fact = 1;
101     for(int i=1;i<=n;++i) fact = (fact * i) % MOD;
102     long long sum = 0;
103     for(int k=0;k<=n;++k) sum = (sum + row[k]) % MOD;
104     cout << "Check: sum_k {" << n << "\\brack k} (mod) = " << sum << ", n! (mod) = " << fact << "\n";
105 
106     return 0;
107 }
108

This program computes the whole row {n \brack 0..n} by forming the polynomial P(x) = x(x+1)...(x+n−1). Using a divide-and-conquer product tree with NTT-based convolution yields an O(n log^2 n) algorithm. The coefficients of P are exactly the unsigned Stirling numbers of the first kind.

Time: O(n log^2 n)Space: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute unsigned {n\brack k} and signed s(n,k) modulo MOD up to N
5	// Recurrence (unsigned): {n\brack k} = (n-1){n-1\brack k} + {n-1\brack k-1}
6	// Signed relation: s(n,k) = (-1)^{n-k} {n\brack k}
7
8	static const int MOD = 998244353; // NTT-friendly prime; works well for modular computations
9
10	int addmod(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
11	int submod(int a, int b){ a -= b; if(a < 0) a += MOD; return a; }
12	int mulmod(long long a, long long b){ return int((a * b) % MOD); }
13
14	int modpow(long long a, long long e){ long long r=1%MOD; a%=MOD; while(e){ if(e&1) r=ra%MOD; a=aa%MOD; e>>=1; } return (int)r; }
15
16	int main(){
17	ios::sync_with_stdio(false);
18	cin.tie(nullptr);
19
20	int N = 10; // build up to N; adjust as needed
21
22	vector<vector<int>> s1u(N+1, vector<int>(N+1, 0)); // unsigned {n\brack k}
23	s1u[0][0] = 1;
24	for(int n=1; n<=N; ++n){
25	for(int k=1; k<=n; ++k){
26	int term1 = mulmod(n-1, s1u[n-1][k]);
27	int term2 = s1u[n-1][k-1];
28	s1u[n][k] = addmod(term1, term2);
29	}
30	}
31
32	// Build signed table via sign relation: s(n,k) = (-1)^{n-k} {n\brack k}
33	vector<vector<int>> s1s(N+1, vector<int>(N+1, 0)); // signed s(n,k)
34	for(int n=0; n<=N; ++n){
35	for(int k=0; k<=n; ++k){
36	int sign = ((n - k) % 2 == 0) ? 1 : MOD-1; // (-1)^{n-k} mod MOD
37	s1s[n][k] = mulmod(sign, s1u[n][k]);
38	}
39	}
40
41	// Demonstration: print small values
42	cout << "Unsigned Stirling numbers of the first kind {n\\brack k} up to N=" << N << "\n";
43	for(int n=0; n<=N; ++n){
44	for(int k=0; k<=n; ++k){
45	cout << s1u[n][k] << (k==n?'\n':' ');
46	}
47	}
48	cout << "\nSigned Stirling numbers of the first kind s(n,k) up to N=" << N << "\n";
49	for(int n=0; n<=N; ++n){
50	for(int k=0; k<=n; ++k){
51	cout << s1s[n][k] << (k==n?'\n':' ');
52	}
53	}
54
55	// Example query: number of permutations of n=7 with k=3 cycles
56	int n=7, k=3;
57	cout << "{" << n << "\\brack" << k << "} mod MOD = " << s1u[n][k] << "\n";
58	return 0;
59	}
60

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	static const int MOD = 998244353;
5	int addmod(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
6	int submod(int a, int b){ a-=b; if(a<0) a+=MOD; return a; }
7	int mulmod(long long a, long long b){ return int((a*b)%MOD); }
8
9	// Precompute signed Stirling numbers of the first kind s(n,k) up to D
10	vector<vector<int>> signed_stirling1(int D){
11	vector<vector<int>> s(D+1, vector<int>(D+1, 0));
12	s[0][0] = 1;
13	for(int n=1; n<=D; ++n){
14	for(int k=1; k<=n; ++k){
15	// s(n,k) = s(n-1,k-1) - (n-1) s(n-1,k)
16	int term1 = s[n-1][k-1];
17	int term2 = mulmod(n-1, s[n-1][k]);
18	s[n][k] = submod(term1, term2);
19	}
20	}
21	return s;
22	}
23
24	// Given p(x) = sum_{k=0}^d a_k x^k, compute b such that p(x) = sum_{n=0}^d b_n x^{\underline{n}}
25	// Using the relation: a_k = sum_{n=k}^d b_n s(n,k) (upper-triangular system)
26	vector<int> power_to_falling(const vector<int>& a, const vector<vector<int>>& s){
27	int d = (int)a.size() - 1;
28	vector<int> b(d+1, 0);
29	// Back substitution from high degree down to 0; s(n,n) = 1
30	for(int n=d; n>=0; --n){
31	int rhs = a[n];
32	for(int t=n+1; t<=d; ++t){
33	// subtract known contributions b_t * s(t,n)
34	rhs = submod(rhs, mulmod(b[t], s[t][n]));
35	}
36	b[n] = rhs; // since s(n,n) = 1
37	}
38	return b;
39	}
40
41	// Given b for q(x) = sum_{n=0}^d b_n x^{\underline{n}}, compute a for power basis q(x) = sum a_k x^k
42	// Using direct triangular sum: a_k = sum_{n=k}^d b_n s(n,k)
43	vector<int> falling_to_power(const vector<int>& b, const vector<vector<int>>& s){
44	int d = (int)b.size() - 1;
45	vector<int> a(d+1, 0);
46	for(int n=0; n<=d; ++n){
47	for(int k=0; k<=n; ++k){
48	a[k] = addmod(a[k], mulmod(b[n], s[n][k]));
49	}
50	}
51	return a;
52	}
53
54	int main(){
55	ios::sync_with_stdio(false);
56	cin.tie(nullptr);
57
58	// Example polynomial: p(x) = 2 + 3x + 5x^2 + 7x^3
59	vector<int> a = {2,3,5,7};
60	int d = (int)a.size() - 1;
61
62	// Precompute signed Stirling numbers up to degree d
63	auto s = signed_stirling1(d);
64
65	// Convert to falling factorial basis
66	vector<int> b = power_to_falling(a, s);
67
68	// Convert back to power basis to verify round-trip
69	vector<int> a2 = falling_to_power(b, s);
70
71	// Output
72	cout << "Coefficients a_k in power basis:" << '\n';
73	for(int i=0;i<=d;++i) cout << a[i] << (i==d?'\n':' ');
74	cout << "Coefficients b_n in falling factorial basis:" << '\n';
75	for(int i=0;i<=d;++i) cout << b[i] << (i==d?'\n':' ');
76	cout << "Back to power basis (should match a):" << '\n';
77	for(int i=0;i<=d;++i) cout << a2[i] << (i==d?'\n':' ');
78
79	return 0;
80	}
81

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// NTT implementation for modulus 998244353 (primitive root = 3)
5	static const int MOD = 998244353;
6	static const int G = 3;
7
8	int addmod(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
9	int submod(int a, int b){ a-=b; if(a<0) a+=MOD; return a; }
10	int mulmod(long long a, long long b){ return int((a*b)%MOD); }
11	int modpow(long long a, long long e){ long long r=1%MOD; a%=MOD; while(e){ if(e&1) r=ra%MOD; a=aa%MOD; e>>=1; } return (int)r; }
12
13	void ntt(vector<int>& a, bool invert){
14	int n = (int)a.size();
15	static vector<int> rev;
16	static vector<int> roots{0,1};
17	if ((int)rev.size() != n){
18	int k = __builtin_ctz(n);
19	rev.assign(n,0);
20	for(int i=0;i<n;++i){ rev[i]=(rev[i>>1]>>1)\|((i&1)<<(k-1)); }
21	}
22	if ((int)roots.size() < n){
23	int k = __builtin_ctz(roots.size());
24	roots.resize(n);
25	while ((1<<k) < n){
26	int z = modpow(G, (MOD-1)>>(k+1));
27	for(int i=1<<(k-1); i<(1<<k); ++i){
28	roots[2*i] = roots[i];
29	roots[2*i+1] = mulmod(roots[i], z);
30	}
31	++k;
32	}
33	}
34	for(int i=0;i<n;++i){ if(i<rev[i]) swap(a[i], a[rev[i]]); }
35	for(int len=1; len<n; len<<=1){
36	for(int i=0; i<n; i+=2*len){
37	for(int j=0; j<len; ++j){
38	int u = a[i+j];
39	int v = mulmod(a[i+j+len], roots[len+j]);
40	a[i+j] = addmod(u, v);
41	a[i+j+len] = submod(u, v);
42	}
43	}
44	}
45	if(invert){
46	reverse(a.begin()+1, a.end());
47	int inv_n = modpow(n, MOD-2);
48	for(int &x: a) x = mulmod(x, inv_n);
49	}
50	}
51
52	vector<int> multiply(vector<int> a, vector<int> b){
53	int need = (int)a.size() + (int)b.size() - 1;
54	int n=1; while(n<need) n<<=1;
55	a.resize(n); b.resize(n);
56	ntt(a,false); ntt(b,false);
57	for(int i=0;i<n;++i) a[i] = mulmod(a[i], b[i]);
58	ntt(a,true);
59	a.resize(need);
60	return a;
61	}
62
63	// Build polynomial P(x) = prod_{i=L}^{R-1} (x + i) via divide-and-conquer
64	vector<int> build_product(int L, int R){
65	if(R - L == 1){
66	// (x + L) => coefficients [L, 1]
67	return vector<int>{ (L%MOD + MOD)%MOD, 1 };
68	}
69	int M = (L + R) >> 1;
70	auto left = build_product(L, M);
71	auto right = build_product(M, R);
72	return multiply(left, right);
73	}
74
75	// Compute the unsigned Stirling numbers of the first kind for a fixed n as a vector of size n+1
76	// They are exactly the coefficients of x(x+1)...(x+n-1)
77	vector<int> stirling1_unsigned_row_fast(int n){
78	if(n==0) return vector<int>{1};
79	auto P = build_product(0, n); // product (x + 0)(x + 1)...(x + n-1)
80	// Note: factor (x+0) = x ensures degree n and zero constant term
81	// P[k] is coefficient of x^k; equals {n\brack k}
82	// Ensure size n+1
83	if((int)P.size() < n+1) P.resize(n+1, 0);
84	return P;
85	}
86
87	int main(){
88	ios::sync_with_stdio(false);
89	cin.tie(nullptr);
90
91	int n = 8;
92	auto row = stirling1_unsigned_row_fast(n);
93
94	cout << "Unsigned Stirling numbers of the first kind for n=" << n << "\n";
95	for(int k=0;k<=n;++k){
96	cout << "{" << n << "\\brack" << k << "} = " << row[k] << "\n";
97	}
98
99	// Sanity check: coefficient sum at x=1 equals n! (since 1^{\overline{n}} = n!)
100	long long fact = 1;
101	for(int i=1;i<=n;++i) fact = (fact * i) % MOD;
102	long long sum = 0;
103	for(int k=0;k<=n;++k) sum = (sum + row[k]) % MOD;
104	cout << "Check: sum_k {" << n << "\\brack k} (mod) = " << sum << ", n! (mod) = " << fact << "\n";
105
106	return 0;
107	}
108