問題概要

「良い数列」とは次の条件を満たす正の整数列のことである。
- 任意の $k > 1, k \in (a_i)$ に対して、 $( k-1 , k )$ を部分列に含む。

正整数 $N$ が与えられるので、
各 $1 \le k \le N$ に対して、次の問題を解いてください。

すべての長さ $N$ の「良い数列」に $k$ は何回登場するか。

制約

$N\le 5000$

考察

まず、良い数列がどのような性質を持っているかを考えよう。
長さ $n$ の良い数列の集合を $s_n$ で書く。
$(a_i) \in s_n$ を一つ fix する。
$A = \max (a_i)$ とすると、 $\{a_i\} = \{1, \cdots A \}$ であることはすぐにわかる。

ところで、サンプルに注目すると、 $|s_n|$ は $1,2,6, \cdots$ となっていることがわかる。
ここで、 $|s_n| = n!$ と仮定して、 $s_n$ を構成してみる。

次のように良い数列を帰納的に構成する操作を考える。

長さ $n$ 良い数列がある。次の要素を挿入する場所を全部の隙間 $n+1$ 箇所の中から選び、挿入後も良い数列であるような数のうち、最大のものを挿入する。

例えば、今、
$(2,3,3,1,2)$ という数列の $2$ と $3$ の間に要素を挿入するとする。
左に $3$ は存在しないため、挿入できる最大の要素は $3$ である。そのため、挿入後の数列は
$(2,3,3,3,1,2)$ のようになる。
長さ $n$ の数列には挿入個所の候補が $n+1$ 箇所あるため、このような操作の列で長さ $n$ の数列を作るとき、 $n!$ 通りの操作列が存在する。
ところで、新しく挿入する要素が現在の数列の $\max$ か $\max + 1$ であることから、異なる操作列からは異なる数列が生成される。
なぜなら、相異なる数列に要素を一つ挿入して等しい数列になるとすると、より右側に挿入している要素の最大性に矛盾するからである。

f:id:no_imi:20200513220458p:plain

(二つが等しいなら、下の図では $a$ ではなく $a+1$ が挿入できるはずである。)

逆は簡単で、良い数列を固定したとき、操作列は一意に復元できる。
例えば、
$(4,2,3,4,1,1,2)$ という良い数列があった時、挿入された順番は
$(7,4,5,6,2,1,3)$ である。(より小さい数字が先、同じ数字の中では右から左の順に追加されている。)

これにより、長さ $n$ の順列と長さ $n$ の良い数列の間に全単射を見出すことができた。

解法

観察
- 良い数列 $(a_i)$ に対応する順列を $(p_i)$ と置く。 $i \lt j$ , $p _ j = p _ i + 1$ の時、 $a_j = a_i + 1$ となっている。つまり、直前より右に挿入したときに限り、要素の値が増える、ということである。

$d _ {i,j}$ を長さ $i$ の良い数列で最大の要素が $j$ 以上なものの数、と定義する。

上の観察により、 $+ 1$ されるような組を $j-1$ 個固定すればよいことがわかる。
このような組を辺で結ぶと、全体が $i-j+1$ 個の連結成分に分けられる。
連結成分内での順番は一意 (左から順) なため、 $i-j+1$ 個の連結成分の順番を定めてあげれば、元の順列、数列が復元できます。
f:id:no_imi:20200513224240p:plain
上は $i = 6, j = 4$ の例です。(inkscape で描くのが面倒になったんで手書きにしました、ごめん())

さて、このように分ける方法は何通りあるでしょうか？
区別のつく $i$ 個のボールを区別のつく $i-j+1$ 個の箱に、一つ以上ずつ分ける場合の数に等しく、これは
\begin{equation} \sum_{k = 1}^{k=i-j+1} (-1)^{i-j+1-k} \dbinom{i-j+1}{k} \times k^{i} = S(i,i-j+1) \times (i-j+1)! \end{equation}

に等しいことが知られています。( $S$ は第二種スターリング数)

これと、包除原理を適用して、すべての良い数列の中で $t$ の登場する回数を求めてみます。
$t$ が数列の $i$ 番目に登場する場合の数は

(長さ $i$ の数列で最大の要素が $t$ なものの数) $\times (i+1)\cdots N$
となります。これは $d _ {i,j}$ 達を包除してあげることで求めることができます。

式は以下のようになります。

\begin{align} ans_t &= \sum _ {i=1} ^ {N} \left(\sum _ {j=t} ^ {i} (-1) ^ {j-t} \dbinom{j-1}{t-1} (i-j+1)! S(i,i-j+1) \right)\times \frac{n!}{i!} \\
&= \frac{n!}{(t-1)!} \sum _ {i=1} ^ {N} \sum _ {j=t} ^ {i} (-1)^{j-t} \frac{(j-1)! \, (i-j+1)! S(i,i-j+1)}{(j-t)! \, i!} \\
&= \frac{n!}{(t-1)!} \sum _ {j=t} ^ {N} \frac{(-1) ^ {j-t} \, (j-1)!}{(j-t)!} \sum _ {i=j} ^ {i=n} \frac{(i-j+1)! \, S(i,i-j+1)}{i!} \\ \end{align}

スターリング数は $O\left( N ^ 2 ) \right)$ で列挙することができます。よって、各 $t$ に対して答えを $O\left( N ^ 2 \right)$ で求めることが出来ました。
ところで最後の式の二つ目の Σ の中には $t$ が現れていないので、前計算することで高速化が出来ます。
よって、全体での計算量が $O\left(N ^ 2 \right)$ となり、この問題を解くことが出来ました。

実装方針

ここまで来たらどう書いてもかわんないって

ソースコード

vector<vmint> StirlingTable(int n){
    vector<vmint> res(n+1,vmint(n+1));
    res[0][0] = 1;
    rep2(i,1,n)rep2(j,1,i){
        res[i][j] = res[i-1][j-1] + res[i-1][j] * j;
    }
    return res ;
}

mint sgn(int x){ return (x&1 ? -1:1);}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);
    calc();
    int n = in();
    auto S = StirlingTable(n);
    vmint T(n+1);
    // 二項目を前計算
    rep2(j,1,n){
        rep2(i,j,n){
            T[j] += prd[i-j+1] * S[i][i-j+1] * invprd[i];
        }
    }
    // 各 t について答えを求める
    rep2(t,1,n){
        mint ans = 0;
        rep2(j,t,n){
            ans += sgn(j-t) * prd[j-1] * invprd[j-t] * T[j];
        }
        cout << ans * prd[n] * invprd[t-1] << " ";
    }

                
}