問題を解いている途中に出会ったので勉強したことをメモします。CP 以外のことは知りません。
定義と性質
定義
Eulerian Number $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k}$ は、以下の条件を満たす長さ $n$ の順列 $P$ の個数である。
- $P_i \leq P_{i + 1}$ であるような $i \ (1 \leq i \leq n \mathrel{-} 1)$ がちょうど $k$ 個存在する
性質
$n < 0, k < 0, n \geq k$ については全て $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k} = 0$ということにします。
- $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{0} = 1$
$P = (n, n \mathrel{-} 1, \dots ,1)$ のみなのでそれはそうです。
- $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k} = (n \mathrel{-} k) \genfrac\langle\rangle{0pt}{}{n \mathrel{-} 1}{k \mathrel{-} 1} + (k + 1) \genfrac\langle\rangle{0pt}{}{n \mathrel{-} 1}{k}$
これは長さ $n \mathrel{-} 1$ の順列 $p$ に $n$ を挿入するときのことを考えます。
挿入したあと $n$ が $i$ 番目の要素になるとします。このとき、 $p_j \leq p_{j + 1}$ であるような $j$ の個数の変化は以下のようになります。
- $i = 1$ なら変わらない、$i = n$ なら $1$ 増える
- どちらでもない場合、 $p_{i \mathrel{-} 1} < p_{i}$ なら変わらない、$p_{i \mathrel{-} 1} > p_i$ なら $1$ 増える
これをまとめると上の式になります。(終)
- $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k} = \genfrac\langle\rangle{0pt}{}{n}{n \mathrel{-} k}$
逆順の順列、もしくは $x$ を $n \mathrel{-} x + 1$ に置き換えた順列を考えれば、一対一対応することがわかります。もちろん、定義の $P_j < P_{j + 1}$ の部分の不等号を逆向きにしてもよいこともわかります。
- $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k} = \sum_{i=0}^{k} (-1)^i \binom{n+1}{i} (k + 1 \mathrel{-} i)^n$
Inclusion-Exclusion らしい形をしているが、自分はこういうのが苦手なのでうまいこと組み合わせ的な解釈をできなかった。できる人がいたら教えて下さい。(問題例に上げたやつの解説以外で、うまく離散的な解釈を…)
以下追記: 25/02/18
競技プログラミングにおいて
計算 (mod)
$n, k$ が与えられて $\displaystyle \genfrac\langle\rangle{0pt}{}{a}{b} \ (a \leq n, b \leq k)$ を全て計算したいとき、漸化式を用いて $O(nk)$ で計算ができます。
$n, k$ が与えられて $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k}$ を計算したいとき、上の公式を用いて $O(n \log n)$ で計算できます。
$n$ が与えられるので $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k} \ (0 \leq k \leq n)$ を全て計算したいとします。$\displaystyle a_i = (-1)^n \binom{n + 1}{i} \ (0 \leq i \leq n), b_i = (i + 1)^n$ とすると $\displaystyle \genfrac\langle\rangle{0pt}{}{n}{k} = \sum_{i=0}^{k} a_ib_{k-i}$ なので、多項式乗算の形になって $O(n \log n)$ で計算できます。
問題例
Upsolve 用 (ネタバレ注意… そのまま問題なのでこの記事自体がネタバレですが)
どちらもオンサイト OI です。前者は $(n, k)$ が与えられたときの答えを求める問題で、解説は別の考察で解いています。後者は FFT + これで、本番で出会った人かわいそうです。(中国の OI 自体そういう競技かもしれません)
コメント