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

• 問題

$2(s_1+n_1+u_1+k_1+e_1)+\Delta s + \Delta n + \Delta u + \Delta k + \Delta e \le N$で各変数は非負という条件下で$\Delta s\Delta n\Delta u\Delta k\Delta e$の総和を取る問題。

$d = N - (\Delta s + \Delta n + \Delta u + \Delta k + \Delta e )$とするとき、$\Delta s\Delta n\Delta u\Delta k\Delta e$は$s_1+n_1+u_1+k_1+e_1 \le d/2$の非負整数解の数だけ足される。これは$\binom{\lfloor d/2 \rfloor)+5}{5}$通りだから、求める数は

$$\sum_{d_1+d_2+d_3+d_4+d_5 + d = N}\binom{\lfloor d/2 \rfloor+5}{5}d_1d_2d_3d_4d_5$$

に等しい。FPSで考えるなら、$\sum_n nx^n = x/(1-x)^2$を5乗して$\sum_{i} \binom{\lfloor i/2 \rfloor +5}{5}x^{i}$という謎の級数を掛けると、$x^N$の係数が求める数である。後者にBerlekamp-Massey法を適用してみると21次の多項式を分母とする有理式が出てくるので、$x^N$の係数はBostan-Mori法で求まる。

---

そもそも一般に$\lfloor i/2 \rfloor$の多項式を係数にするFPSが有理べき級数になるのかどうかとか、基本的なことがよくわかっていなかった。

与えられたFPS$f(x)$の偶数項、奇数項がそれぞれ有理べき級数$g(x), h(x)$の偶数項、奇数項と一致しているなら、$g$の(0-basedで)偶数項だけ抜き出したもの$(g(x)+g(-x))/2$と$h$の奇数項だけ抜き出したもの$(h(x)-h(-x))/2$を足せば$f(x)$になるので、確かに有理べき級数になる。一般に$\lfloor i/k \rfloor$の多項式を係数とするFPSについても、$1$の$k$乗根を考えれば同じことが言える。

一般化すると、次の性質を満たす$f(x) = \sum_n a_n x^n$は有理べき級数と言える:

$M$個の有理べき級数$f_k(x) = \sum_n b_{k, n}x^n \ (k=0, 1, ..., M-1)$と$N \in \mathbb N$が存在して、$n \ge N$ならば$a_n = b_{n \bmod M, n}$。