エイシングプログラミングコンテスト 2020 F - Two Snuke

公式解説とは違う解法です。

解法

$N \lt 5$ のときは答えは $0$ なので、 $N \ge 5$ とします。

まずは $O(N)$ 解法を

まず答えを $O(N)$ で求める方法を考えます。

$s_{1} + n_{1} + u_{1} + k_{1} + e_{1}$ の値を $x$ として、これを全通り試しましょう。そうすると、この $x$ を $5$ つに分ける分け方が $_{x+4}C_{4}$ 通りあります。 $x$ 個並んだボールを $4$ 本の仕切りで $5$ つの領域に分ける場合の数です。

$s = s_{2} - s_{1}$ として、 $n, u, k, e$ も同様に定義します。そうすると「全部足して $N$ 以下」という条件は $s + n + u + k + e \le N-2x$ と表記することができます。これを満たす $(s, n, u, k, e)$ の組それぞれについて $snuke$ （人名ではなく積です）を計算し、全て合計したものを求めたいです。これは、以下のような場合の数と等しくなります。

$N-2x$ 個のボールに $5$ 本の仕切りを入れて $s, n, u, k, e, (あまり)$ の $6$ つの領域に分け、さらに $s, n, u, k, e$ に相当する $5$ つの領域から $1$ つずつのボールを選ぶような場合の数。

これは言い換えると、ボールと仕切りを並べる合計 $N-2x+5$ 箇所のスペースから、仕切りと選んだボールに相当する $10$ 箇所を選び、その $10$ 箇所には左から順に「選んだボール、仕切り、…、選んだボール、仕切り」と割り当てるような場合の数に等しいです。つまり、この値は $_{N-2x+5}C_{10}$ と計算できます。

$x$ の範囲としては $s, n, u, k, e$ が全て正になれるもの、つまり $N-2x \ge 5$ である範囲を考えます。そうすると答えは

$\displaystyle \sum_{x=0}^{\lfloor\frac{N-5}{2}\rfloor} \left({}_{x+4}C_{4} \times {}_{N-2x+5}C_{10}\right)$

と計算することができます。階乗を前計算して $x$ についてループを回すことで $O(N)$ で解くことができますが、間に合いません。

偶奇に分けて多項式と見る

先ほどのシグマの中身を見てみましょう。 ${}_{x+4}C_{4}$ という値は、具体的には $\frac{1}{24}(x+4)(x+3)(x+2)(x+1)$ という $x$ についての $4$ 次多項式です。同様に ${}_{N-2x+5}C_{10}$ は $(N-2x)$ についての $10$ 次多項式です。つまりシグマの中身は $x$ と $N$ についての $14$ 次多項式です。より正確には、全ての項で $x$ と $N$ の次数合計が $14$ 以下であるような多項式となっています。

ここで重要な性質として、 $x$ についての $d$ 次多項式の値を $x=0, ..., n$ まで合計したものは $n$ についての $d+1$ 次多項式になります。

今回の計算式におけるループ終端は $\lfloor\frac{N-5}{2}\rfloor$ でした。このままでは扱いにくいので $N$ の偶奇で場合分けします。例えば $N$ が奇数である場合、 $n = \frac{N-5}{2}$ と置きます。そうするとループの終端は $n$ となり、 $N$ を $2n+5$ で置き換えるとシグマの中身は $x$ と $n$ についての $14$ 次多項式になります。先ほどの性質から、このシグマを処理した結果は $n$ についての $15$ 次多項式になることが分かります。

具体的に冪乗和の公式を当てはめて大量の計算をすればこの多項式の係数が求められますが、絶対にやりたくないです。「ラグランジュ補間」という方法を使いましょう。これは「 $n$ についての $d$ 次多項式 $f(n)$ の自由度は $d+1$ であり、 $d+1$ 通りの相異なる点 $(n, f(n))$ から多項式を一意に決定することができる」という性質を用いるものです。特に相異なる既知の点として $n=0, 1, ..., d$ に対する $f(n)$ を用いた場合、1つの未知の $n$ に対する $f(n)$ の値は $O(d)$ で計算することができます。