Home 组合数学

# 斯特林数，上升幂，下降幂，普通幂的定义

# 第二类斯特林数

n{n0}n\brace 0{n1}n\brace 1{n2}n\brace 2{n3}n\brace 3{n4}n\brace 4{n5}n\brace 5{n6}n\brace 6{n7}n\brace 7{n8}n\brace 8{n9}n\brace9
011000000000000000000
100110000000000000000
200111100000000000000
300113311000000000000
400117766110000000000
500111515252510101100000000
60011313190906565151511000000
7001163633013013503501401402121110000
80011127127966966170117011050105026626628281100
9001125525530253025777077706951695124462446462462363611

定义 {nm}{n\brace m} 表示将 nn 件物品分成 mm 个子集（非空）的方案数。

有

{nm}={n−1m−1}+m{n−1m}{n\brace m} = {n-1\brace m-1} + m{n-1\brace m}

# 第一类斯特林数

n[n0]n\brack 0[n1]n\brack 1[n2]n\brack 2[n3]n\brack 3[n4]n\brack 4[n5]n\brack 5[n6]n\brack 6[n7]n\brack 7[n8]n\brack 8{n9}n\brace9
011000000000000000000
100110000000000000000
200111100000000000000
300223311000000000000
40066111166110000000000
50024245050353510101100000000
6001201202742742252258585151511000000
70072072017641764162416247357351751752121110000
8005040504013068130681313213132676967691960196032232228281100
90040320403201095841095841181241181246728467284224492244945364536546546363611

定义 [nm]n\brack m 表示将 nn 件物品分成 mm 个轮换（非空，圆排列）的方案数。

有

[nm]=(n−1)[n−1m]+[n−1m−1]{n\brack m} = (n-1){n-1\brack m}+{n-1\brack m-1}

# 上升幂，下降幂，普通幂

xn‾=x!(x−n)!xn‾=(x+n−1)!(x−1)!xn=xnxn‾=(x+n−1)n‾xn‾=(x−n+1)n‾\begin{aligned} &x^{\underline{n}} = \frac{x!}{(x-n)!}\\ &x^{\overline{n}} = \frac{(x+n-1)!}{(x-1)!}\\ &x^n = x^n\\ &x^{\overline{n}} = (x+n-1)^{\underline{n}}\\ &x^{\underline{n}} = (x-n+1)^{\overline{n}}\\ \end{aligned}

# 斯特林数的性质

∑i=0n{ni}xi‾=∑i=0n(i{n−1i}+{n−1i−1})xi‾=∑i=0ni{n−1i}xi‾+∑i=0n{n−1i−1}xi‾=∑i=0ni{n−1i}xi‾+∑i=1n{n−1i−1}xi‾=∑i=0ni{n−1i}xi‾+∑i=1n{n−1i−1}x(i−1)+1‾=∑i=0ni{n−1i}xi‾+∑i=0n−1{n−1i}xi+1‾=∑i=0n−1i{n−1i}xi‾+∑i=0n−1{n−1i}xi‾(x−i)=∑i=0n−1i{n−1i}xi‾+{n−1i}xi‾(x−i)=x∑i=0n−1{n−1i}xi‾=x×xn−1=xn\begin{aligned} \sum_{i=0}^{n}{n\brace i}x^{\underline{i}} &= \sum_{i=0}^{n}(i{n-1\brace i}+{n-1\brace i-1})x^{\underline{i}}\\ &= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=0}^{n}{n-1\brace i-1}x^{\underline{i}}\\ &= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=1}^{n}{n-1\brace i-1}x^{\underline{i}}\\ &= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=1}^{n}{n-1\brace i-1}x^{\underline{(i-1)+1}}\\ &= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=0}^{n-1}{n-1\brace i}x^{\underline{i+1}}\\ &= \sum_{i=0}^{n-1}i{n-1\brace i}x^{\underline{i}}+\sum_{i=0}^{n-1}{n-1\brace i}x^{\underline{i}}(x-i)\\ &= \sum_{i=0}^{n-1}i{n-1\brace i}x^{\underline{i}}+{n-1\brace i}x^{\underline{i}}(x-i)\\ &= x\sum_{i=0}^{n-1}{n-1\brace i}x^{\underline{i}}\\ &= x \times x^{n-1} = x^{n}\\ \end{aligned}

∑i=0n[ni]xi=∑i=0n((n−1)[n−1i]+[n−1i−1])xi=∑i=0n(n−1)[n−1i]xi+∑i=0n[n−1i−1]xi=∑i=0n(n−1)[n−1i]xi+∑i=1n[n−1i−1]x(i−1)+1=∑i=0n(n−1)[n−1i]xi+∑i=0n−1[n−1i]xi+1=(n−1+x)∑i=0n[n−1i]xi=(x+n−1)xn−1‾=xn‾\begin{aligned} \sum_{i=0}^{n}{n\brack i}x^{i} &= \sum_{i=0}^{n}((n-1){n-1\brack i}+{n-1\brack i-1})x^i\\ &= \sum_{i=0}^{n}(n-1){n-1\brack i}x^i+\sum_{i=0}^{n}{n-1\brack i-1}x^i\\ &= \sum_{i=0}^{n}(n-1){n-1\brack i}x^i+\sum_{i=1}^{n}{n-1\brack i-1}x^{(i-1)+1}\\ &= \sum_{i=0}^{n}(n-1){n-1\brack i}x^i+\sum_{i=0}^{n-1}{n-1\brack i}x^{i+1}\\ &= (n-1+x)\sum_{i=0}^{n}{n-1\brack i}x^i\\ &= (x+n-1)x^{\overline{n-1}}\\ &= x^{\overline{n}}\\ \end{aligned}

xn‾=(−1)n(−x)n‾=(−1)n∑i=0n[ni](−x)i=∑i=0n[ni](−1)n−ixi\begin{aligned} x^{\underline{n}} &= (-1)^n(-x)^{\overline{n}}\\ &= (-1)^n\sum_{i=0}^{n}{n\brack i}(-x)^i\\ &= \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}x^i\\ \end{aligned}

xn=(−1)n(−x)n=(−1)n∑i=0n{ni}(−x)i‾=(−1)n∑i=0n{ni}(−1)ixi‾=∑i=0n{ni}(−1)n−ixi‾\begin{aligned} x^n &= (-1)^n(-x)^n\\ &= (-1)^n\sum_{i=0}^{n}{n\brace i}(-x)^{\underline{i}}\\ &= (-1)^n\sum_{i=0}^{n}{n\brace i}(-1)^ix^{\overline{i}}\\ &= \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}x^{\overline{i}}\\ \end{aligned}

整理一下

xn=∑i=0n{ni}xi‾xn=∑i=0n{ni}(−1)n−ixi‾xn‾=∑i=0n[ni]xixn‾=∑i=0n[ni](−1)n−ixi\begin{aligned} &x^n = \sum_{i=0}^{n}{n\brace i}x^{\underline{i}}\\ &x^n = \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}x^{\overline{i}}\\ &x^{\overline{n}} = \sum_{i=0}^{n}{n\brack i}x^i\\ &x^{\underline{n}} = \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}x^i\\ \end{aligned}

表示普通幂时用第二类斯特林数，表示上升幂、下降幂时用第一类斯特林数，用大数表示小数时用 (−1)n−i(-1)^{n-i}。

考虑公式的嵌套，让斯特林数更毒瘤：

xn=∑i=0n{ni}(−1)n−ixi‾=∑i=0n{ni}(−1)n−i∑m=0i[im]xm=∑m=0nxm∑i=mn{ni}[im](−1)n−i\begin{aligned} x^n &= \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}x^{\overline{i}}\\ &= \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}\sum_{m=0}^i{i\brack m}x^{m}\\ &= \sum_{m=0}^{n}x^{m}\sum_{i=m}^{n}{n\brace i}{i\brack m}(-1)^{n-i} \end{aligned}

∑i=mn{ni}[im](−1)n−i=[n=m]\sum_{i=m}^{n}{n\brace i}{i\brack m}(-1)^{n-i} = [n=m]

xn‾=∑i=0n[ni](−1)n−ixi=∑i=0n[ni](−1)n−i∑j=0i{ij}xj‾=∑j=0ixj‾∑i=jn[ni]{ij}(−1)n−i\begin{aligned} x^{\underline{n}} &= \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}x^{i}\\ &= \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}\sum_{j=0}^{i}{i\brace j}x^{\underline{j}}\\ &= \sum_{j=0}^{i}x^{\underline{j}}\sum_{i=j}^{n}{n\brack i}{i\brace j}(-1)^{n-i}\\ \end{aligned}

∑i=mn[ni]{im}(−1)n−i=[m=n]\sum_{i=m}^{n}{n\brack i}{i\brace m}(-1)^{n-i} = [m=n]

既然有二项式反演，也有斯特林反演！

g(n)=∑i=0n{ni}f(i)⟺f(n)=∑i=0n[ni](−1)n−ig(i)g(n)=∑i=0n[ni]f(i)⟺f(n)=∑i=0n{ni}(−1)n−ig(i)\begin{aligned} g(n)=\sum_{i=0}^{n}{n\brace i}f(i) &\iff f(n) = \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}g(i)\\ g(n)=\sum_{i=0}^{n}{n\brack i}f(i) &\iff f(n) = \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}g(i)\\ \end{aligned}

证明略。

在来个柿子：

xn=∑i=0x{ni}(xi)i!x^n = \sum_{i=0}^{x}{n\brace i}\dbinom{x}{i}i!

考虑组合意义来解释， xnx^n 表示将 nn 个小球放进 xx 个盒子的方案数， ∑i=0x\sum_{i=0}^{x} 表示有几个盒子非空，(xi)\tbinom{x}{i} 表示选哪几个盒子非空， i!i! 表示非空盒子的顺序， {ni}{n\brace i} 表示 nn 个小球划分成 ii 个集合的方案数。

二项式反演可得：

xn=∑i=0x{ni}(xi)i!⟺{nm}m!=∑i=0m(mi)(−1)m−iinx^n = \sum_{i=0}^{x}{n\brace i}\dbinom{x}{i}i! \iff {n\brace m}m! = \sum_{i=0}^{m}\dbinom{m}{i}(-1)^{m-i}i^n

{nm}=∑i=0m(mi)(−1)m−iinm!=∑i=0mm!i!(m−i)!m!(−1)m−iin=∑i=0min(−1)m−ii!(m−i)!=∑i=0mini!×(−1)m−i(m−i)!\begin{aligned}{n\brace m} &= \sum_{i=0}^{m}\frac{\tbinom{m}{i}(-1)^{m-i}i^n}{m!}\\&=\sum_{i=0}^{m}\dfrac{m!}{i!(m-i)!m!}(-1)^{m-i}i^n\\&=\sum_{i=0}^{m}\dfrac{i^n(-1)^{m-i}}{i!(m-i)!}\\&=\sum_{i=0}^{m}\dfrac{i^n}{i!}\times\dfrac{(-1)^{m-i}}{(m-i)!}\end{aligned}

可以发现这是个卷积， NTTNTT 即可计算同一行的第二类斯特林数。

# 例题

P6620 [省选联考 2020 A 卷] 组合数问题

遇到不可以直接计算的多项式、组合数计数题时可以考虑普通幂转下降幂或上升幂。

(∑k=0nf(k)xk(nk))modp=∑i=0m∑k=0nbiki‾xk(nk)=∑i=0m∑k=0nbini‾xk(n−ik−i)=∑i=0mbini‾∑k=0n(n−ik−i)xk=∑i=0mbini‾∑k=0n−i(n−ik−i)xk1n−i−k=∑i=0mbini‾xi∑k=0n−i(n−ik)xk1n−i−k=∑i=0mbini‾xi(x+1)n−i\begin{aligned} (\sum_{k=0}^{n}f(k)x^k\dbinom{n}{k}) \bmod p &=\sum_{i=0}^{m}\sum_{k=0}^{n}b_ik^{\underline{i}}x^k\dbinom{n}{k}\\ &=\sum_{i=0}^{m}\sum_{k=0}^{n}b_in^{\underline{i}}x^k\dbinom{n-i}{k-i}\\ &=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n}\dbinom{n-i}{k-i}x^k\\ &=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n-i}\dbinom{n-i}{k-i}x^k1^{n-i-k}\\ &=\sum_{i=0}^{m}b_in^{\underline{i}}x^{i}\sum_{k=0}^{n-i}\dbinom{n-i}{k}x^k1^{n-i-k}\\ &=\sum_{i=0}^{m}b_in^{\underline{i}}x^{i}(x+1)^{n-i}\\ \end{aligned}

其中

f(x)=∑i=0mbixi‾\begin{aligned} f(x) = \sum_{i=0}^{m}b_ix^{\underline{i}} \end{aligned}

有

f(x)=∑i=0maixi=∑i=0mai∑j=0i{ij}xj‾=∑j=0mxj‾∑i=jm{ij}ai\begin{aligned} f(x) &= \sum_{i=0}^{m}a_ix^i\\ &= \sum_{i=0}^{m}a_i\sum_{j=0}^{i}{i\brace j}x^{\underline{j}}\\ &= \sum_{j=0}^{m}x^{\underline{j}}\sum_{i=j}^{m}{i\brace j}a_i\\ \end{aligned}

第二类斯特林数直接暴力 m2m^2 计算即可，总时间复杂度为 O(m2)O(m^2)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 3001;
ll stirling[N][N], MOD;
void get_stirling(ll tt){
  stirling[0][0]=1;
  for(ll i = 1; i <= tt; i++)
    for(ll j = 1; j <= i; j++)
      stirling[i][j] = 1ll*(1ll*stirling[i-1][j]*j%MOD+1ll*stirling[i-1][j-1]) % MOD;
}
ll my_pow(ll x, ll y){
  ll res = 1;
  for(;y;y>>=1,x=x*x%MOD)
    if(y&1)res=res*x%MOD;
  return res;
}
ll n, X, m;
ll a[N], b[N];
int main(){
  cin>>n>>X>>MOD>>m;
  get_stirling(m);
  for(ll i = 0; i <= m; i++)
    cin>>a[i];
  for(ll i = 0; i <= m; i++)
    for(ll j = i; j <= m; j++)
      b[i] = (b[i]+stirling[j][i]*a[j]%MOD)%MOD;
  ll ans = 0;
  for(ll i = 0, now = 1; i <= m; i++){
    ll res = b[i] * now % MOD * my_pow(X, i) % MOD * my_pow(X+1, n-i) % MOD;
    ans = (ans + res) % MOD;
    now = now * (n-i) % MOD;
  }
  cout<<(ans+MOD)%MOD<<endl;
  return 0;
}

P5395 第二类斯特林数・行

xn=∑i=0x{ni}(xi)i!x^n = \sum_{i=0}^{x}{n\brace i}\dbinom{x}{i}i!

考虑组合意义来解释， xnx^n 表示将 nn 个小球放进 xx 个盒子的方案数， ∑i=0x\sum_{i=0}^{x} 表示有几个盒子非空，(xi)\tbinom{x}{i} 表示选哪几个盒子非空， i!i! 表示非空盒子的顺序， {ni}{n\brace i} 表示 nn 个小球划分成 ii 个集合的方案数。

二项式反演可得：

xn=∑i=0x{ni}(xi)i!⟺{nm}m!=∑i=0m(mi)(−1)m−iinx^n = \sum_{i=0}^{x}{n\brace i}\dbinom{x}{i}i! \iff {n\brace m}m! = \sum_{i=0}^{m}\dbinom{m}{i}(-1)^{m-i}i^n

{nm}=∑i=0m(mi)(−1)m−iinm!=∑i=0mm!i!(m−i)!m!(−1)m−iin=∑i=0min(−1)m−ii!(m−i)!=∑i=0mini!×(−1)m−i(m−i)!\begin{aligned}{n\brace m} &= \sum_{i=0}^{m}\frac{\tbinom{m}{i}(-1)^{m-i}i^n}{m!}\\&=\sum_{i=0}^{m}\dfrac{m!}{i!(m-i)!m!}(-1)^{m-i}i^n\\&=\sum_{i=0}^{m}\dfrac{i^n(-1)^{m-i}}{i!(m-i)!}\\&=\sum_{i=0}^{m}\dfrac{i^n}{i!}\times\dfrac{(-1)^{m-i}}{(m-i)!}\end{aligned}

可以发现这是个卷积， NTTNTT 即可计算同一行的第二类斯特林数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 167772161;
const ll N = 1e6 + 11;
ll rev[N], w[N], gen = 3;
ll my_pow(ll x, ll y){
  ll res = 1;
  for(;y;y>>=1,x=x*x%MOD)
    if(y&1)res=res*x%MOD;
  return res;
}
void NTT(ll *a, ll Len, bool type){
  for(int i = 0; i < Len; i++){
    rev[i] = (rev[i>>1]>>1) + (i&1?Len>>1:0);
    if(rev[i]>i)swap(a[rev[i]], a[i]);
  }
  for(ll d = 1; d < Len; d <<= 1){
    ll W = my_pow(gen, (MOD-1)/(d*2));
    if(type) W = my_pow(W, MOD-2);
    w[0] = 1;
    for(ll i = 1; i < d; i++)
      w[i] = w[i-1] * W % MOD;
    for(ll fir = 0; fir < Len; fir += (d*2)){
      ll sec = fir + d;
      for(ll i = 0 ; i < d; i++){
        ll a0 = a[fir+i], a1 = a[sec+i]*w[i]%MOD;
        a[fir+i] = (a0+a1)%MOD;
        a[sec+i] = (a0-a1+MOD)%MOD;
      }
    }
  }
  if(type){
    ll invlen=my_pow(Len, MOD-2);
    for(int i=0; i<Len; i++)
      a[i] = a[i]*invlen%MOD;
  }
}
ll f[N], g[N], fac[N], ifac[N], n;
ll fu(int k){return k&1?-1:1;}
int main(){
  cin>>n;
  ifac[0]=fac[0]=1;
  for(ll i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
  ifac[n] = my_pow(fac[n], MOD-2);
  for(ll i = n-1; i; i--) ifac[i] = ifac[i+1] * (i+1) % MOD;
  for(ll i = 0; i <= n; i++){
    f[i] = fu(i)*ifac[i]%MOD, f[i] = (f[i]+MOD)%MOD;
    g[i] = my_pow(i, n) * ifac[i] % MOD;
    // cout << f[i] << " " << g[i] << endl;
  }
  ll len = 1;
  while(len<=(n*2))len<<=1;
  NTT(f, len, 0), NTT(g, len, 0);
  for(int i = 0; i < len; i++)
    f[i] = f[i] * g[i] % MOD, f[i] = (f[i] + MOD) % MOD;
  NTT(f, len, 1);
  for(int i = 0; i <= n; i++)
    cout << f[i] << " ";
  cout << endl;
  return 0;
}

P5408 第一类斯特林数・行

有

xn‾=∑i=0n[ni]xix^{\overline{n}} = \sum_{i=0}^{n}{n\brack i}x^i

考虑倍增：

x2n‾=xn‾(x+n)n‾x^{\overline{2n}} = x^{\overline{n}}(x+n)^{\overline{n}}

假设我们求出了 xn‾x^{\overline{n}} 的多项式表达 f1f1 。

现在要求 (x+n)n‾(x+n)^{\overline{n}} 的多项式表达 f2f2 。

有:

f1(x)=f2(x−n)f1(x) = f2(x-n)

设 aia_i 为 f1f1 的系数，有：

f2=∑i=0nai(x+n)i=∑i=0nai∑j=0ixjni−j(ij)=∑j=0nxj∑i=jnni−jaii!j!(i−j)!=∑j=0nxjj!∑i=jnaii!ni−j(i−j)!\begin{aligned} f2 &= \sum_{i=0}^{n}a_i(x+n)^i\\ &= \sum_{i=0}^{n}a_i\sum_{j=0}^{i}x^jn^{i-j}\dbinom{i}{j}\\ &= \sum_{j=0}^{n}x^j\sum_{i=j}^{n}n^{i-j}a^i\dfrac{i!}{j!(i-j)!}\\ &= \sum_{j=0}^{n}\dfrac{x^j}{j!}\sum_{i=j}^{n}a^ii!\dfrac{n^{i-j}}{(i-j)!}\\ \end{aligned}

可以发现里面是个卷积， NTTNTT 计算即可。

注意卷积时 LenLen 的长度不能大也不能小（代码第 4848 行）。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 167772161;
const ll N = 7e5, gen=3;
ll my_pow(ll x, ll y){
  ll res = 1;
  for(;y;y>>=1,x=x*x%MOD)
    if(y&1)res=res*x%MOD;
  return res;
}
ll inv(ll x){
  return my_pow(x, MOD-2);
}
ll rev[N], w[N];
void ntt(ll *a, ll Len, bool type){
  for(ll i = 0 ; i < Len; i++){
    rev[i] = (rev[i>>1]>>1) + (i&1?Len>>1:0);
    if(rev[i]>i)swap(a[rev[i]], a[i]);
  }
  for(ll d=1; d<Len; d<<=1){
    ll W = my_pow(gen, (MOD-1)/(d*2));
    if(type) W = inv(W);
    w[0]=1;
    for(ll i = 1; i < d; i++)
      w[i] = w[i-1] * W % MOD;
    for(ll fir=0; fir<Len; fir+=d*2){
      ll sec=fir+d;
      for(ll i=0; i<d; i++){
        ll a0=a[fir+i], a1=a[sec+i]*w[i]%MOD;
        a[fir+i]=(a0+a1)%MOD;
        a[sec+i]=(a0-a1+MOD)%MOD;
      }
    }
  }
  if(type){
    ll invlen=inv(Len);
    for(ll i=0; i<Len; i++)
      a[i]=a[i]*invlen%MOD;
  }
}
ll aa[N], bb[N];
void mul(ll *a, ll *b, ll alen, ll blen){
  ll len=1;
  while(len<=(alen+blen))len<<=1;// 不能多也不能少！（len=xlen+ylen）
  ntt(a, len, 0);
  ntt(b, len, 0);
  for(int i=0; i<len; i++)
    a[i]=a[i]*b[i]%MOD;
  ntt(a, len, 1);
}
ll ans[N], s[N], A[N], B[N], C[N];
ll fac[N], ifac[N];
void sol_striling_one_line(ll tt){
  if(tt==1){s[1]=1;return;}
  if(tt&1){
    sol_striling_one_line(tt-1);
    for(ll i=tt; i; i--)
      s[i] = (s[i-1] + s[i]*(tt-1)%MOD)%MOD;
    s[0]=s[0]*(tt-1)%MOD;
    return;
  }
  ll slen = tt/2, res=1;
  sol_striling_one_line(slen);
  for(int i=0; i<=slen; i++)
    A[i]=s[i]*fac[i]%MOD,
    B[i]=res*ifac[i]%MOD,
    res=res*slen%MOD;
  reverse(A, A+slen+1);
  mul(A, B, slen+1, slen+1);
  for(int i=0; i<=slen; i++)
    C[i]=A[slen-i]*ifac[i]%MOD;
  mul(s,C,slen+1,slen+1);
  int len=1;
  while(len<=(tt+2))len<<=1;
  for(int i=slen+1; i<len; i++)A[i]=B[i]=C[i]=0;
  for(int i=tt+1; i<len; i++)s[i]=0;
}
void init_fac(int tt){
  fac[0]=ifac[0]=1;
  for(ll i=1; i<=tt; i++)
    fac[i]=fac[i-1]*i%MOD;
  ifac[tt]=my_pow(fac[tt], MOD-2);
  for(ll i=tt-1; i; i--)
    ifac[i] = ifac[i+1]*(i+1)%MOD;
}
ll* striling_first_line(ll tt){
  init_fac(tt<<1);
  memset(A, 0, sizeof A);
  memset(B, 0, sizeof B);
  memset(s, 0, sizeof s);
  memset(C, 0, sizeof C);
  sol_striling_one_line(tt);
  return s;
}
int main(){
  ll n;
  cin>>n;
  ll* striling=striling_first_line(n);
  for(int i=0; i<=n; i++) cout<<striling[i]<<' ';
  cout<<'\n';
  return 0;
}