https://atcoder.jp/contests/aising2020/tasks/aising2020_f

今回はちょっと変則的に解説する。
3種類の方針を解説する。

アルメリアさん解法「積の和を組合せに変換してラグランジュ補間」
公式解説解法「積の和を組合せに変換してDPを作って行列累乗」
形式的冪級数解法「形式的冪級数にして線形漸化式を作って行列累乗」
（4. 幻のO(1)解法）

関係性としては、12は前半まで一緒です。23は後半が一緒です。
TLを見てると次元が色々出てきます。うーん。
なお、以下のアルゴリズム自体は解説しない。
もし分からない場合はこの問題で学ぶより先に、ググって解説記事を読むことをオススメする。

あと非常にアレなんですけど、解説書くので疲れて、
解説2でしか通してません！！！！
たぶんあってると思う。

解法1 アルメリアさん解法「積の和を組合せに変換してラグランジュ補間」

えーいきなりなのですが、アルメリアさんのブログを見て理解しましょう。
エイシングプログラミングコンテスト 2020 F - Two Snuke - ARMERIA
歴史に残る分かりやすさです。

概念抽出

解法の流れとしては2ステップです。

① 積の和を組合せに変換する。
結論だけ書いてしまうと、「f(N) := 答え」とすると、
f(N) = sum_{x=0..(N-5)/2} (C(x+4,4)*C(N-2x+5,10))
であるという変換です。

② ラグランジュ補間をする。
f(N)の多項式表現が得られればそこにNを代入すれば答えが求まる。
ラグランジュ補間を使えばそれが実現できる。

なるほどなぁ

解法2 公式解説解法「積の和を組合せに変換してDPを作って行列累乗」

https://atcoder.jp/contests/aising2020/submissions/15193566

積の和を組合せに変換する

公式解説のdp定義をする直前までで説明しています。
アルメリアさんと考え方は同じなのですが、最終形が少し違います。
こちらでは先頭に2s1とか2n1とかのボールもつけて組合せを考えています。
しかし、そうすると、先頭の5グループは偶数個で構成される必要があり、単純なコンビネーションで計算ができなくなります。
よって、こちらではDPを使って組合せを数え上げることにしています。

DPで組合せを求める…の前にもうちょっと簡単な例

すこし複雑なので、ちょっと簡単なもので考えてみる。
例えば、普通にN個をMグループに分ける組み合わせを計算したいときは、
dp[i][group] := i番目のボールまで処理を終えていて、現在group番目のグループにあるような組合せ
として

rep(i, 0, N) rep(group, 0, M) {
    rep(dest, group, M) dp[i + 1][dest] += dp[i][group];
}

とやって、dp[N][M - 1]が答えになる。グループ内に必ず1個は入れるようにするなら、N -= Mでもして同様の計算をすればいい。
こっちのDPが理解できれば公式解説にあるDPを理解することはそれほど難しくない。

DP

公式解説にあるDPを見てみよう。
dp[i][group][p] := i番目のボールまで処理を終えていて、現在group番目のグループにあって、そのグループの個数のパリティがpであるような組合せ

rep(i, 0, N) rep(group, 0, 16) rep(p, 0, 2) {
    dp[i + 1][group][1 - p] += dp[i][group][p];   
    // 最初の5グループは偶数個になる必要があるので、奇数個であればそれ以降のグループ移動はできない
    if(group < 5 && p == 1) continue;
    rep(dest, group + 1, 16) dp[i + 1][dest][1] += dp[i][group][p];
}

15グループではなくて、16グループに分割しているのは、

1～5グループ：2s1, 2n1…用：偶数個入れる
6～15グループ：Δs, Δn…用：個数とどれを選んだかのためのグループ
16グループ：使わなかったボール（条件がN以下なので）

これで、dp[N][15][0]+dp[N][15][0]が答え。

DPを行列累乗で高速化

DPの更新をよくよく見てみると、dp[i + 1]はdp[i]から中身にかかわらず係数1で遷移が行われていることが分かる。
つまり、更新は毎回同じ行列をかけて計算可能である。
よって、行列累乗で高速化しよう。

行列はgroupで16×pで2なので32要素となる。
圧縮の余地はあるが、さっきのDP更新式を使えば、行列をサクッと作れるので、特にやる必要もないだろう。
あとは、行列に落として行列累乗して、答えを出す。

解法3 形式的冪級数解法「形式的冪級数にして線形漸化式を作って行列累乗」

畳み込みっぽい

まず、なぜ形式的冪級数が出てくるかというと、問題文に出てくる(s2−s1)(n2−n1)(u2−u1)(k2−k1)(e2−e1)の総和と言われたら、
これは畳み込み計算なのでは？という所から発想が始まる。
まあ、その発想については、確かに形似ているねレベルで分かってくれる人もいると思う。
その発想を信じて畳み込みへ突き進むと、形式的冪級数で解けることが分かってくる。

周り道をしてしまったが、もう少しだけ回り道をする。

s1+s2	s2-s1	s2-s1の和
1	1-0=1	1
2	2-0=2	2
3	3-0=3, 2-1=1	4
4	4-0=4, 3-1=2	6
5	5-0=5, 4-1=3, 3-2=1	9
6	6-0=6, 5-1=4, 4-2=2	12

s1+s2の総和とs2-s1の値の和の関係表である。
f[s1+s2] := s2-s1の値の和
のように定義する。
そして、g[x] := f[s1+s2], f[n1+n2], ... の畳み込み
とすると、g[1] + g[2] + ... + g[N]が答えになっている（！！）
これ以上行間を埋めるのが難しいのだが、これを何とか理解してほしい。

もうちょっとだけ蛇足かもしれないが説明すると、N個をs1,s2,n1…とかに分割していくのだが、
f[x] := s1,s2にx個渡したときに作れるs2-s1の和
みたいに考えると、畳みこんだ先で、
g[x] := x個を分割したときの(s2−s1)(n2−n1)(u2−u1)(k2−k1)(e2−e1)の和
になってくれる感じ

形式的冪級数へ

ここまで分かれば峠は越えた感じがする。
あとは、典型を適用していく。
配列の畳み込み計算は形式的冪級数に変換すると掛け算で処理可能なので、形式的冪級数に変換する。
あの短時間で通したのにmaspyさんは探索的に0から探していて化け物じみたムーブをしているのだが、
凡人の自分はとりあえず、いつものアレで探してみた。
A002620 - OEIS

f(x) = 1/( (1-x)²*(1-x²))

さて、畳み込みをするが、snukeのどれも同じ形になるので累乗するだけ。

g(x) = {f(x)}^5

それで、今回得たい答えは、更に累積和になっている。
形式的冪級数で母関数の累積和を取りたいときは、×1/(1-x)をすればいいので、

ans(x) = {f(x)}^5 / (1-x)
ans(x) = 1 / {(1-x)¹⁶ * (1+x)⁵}

やっとTLで見かけたような形になってきましたね…

線形漸化式に変換する

分母を展開して、多項式を作ると、それがそのまま線形漸化式になってるので、行列に変換して、行列累乗して答えを出します。
（もうここまで解説書いて力尽きました）
違ってたらごめんなさい。
uwiさんのコードを見るのがオススメです。
[多項式・形式的べき級数]（３）線形漸化式と形式的べき級数 | maspyのHP
ここもオススメ。

maspyさんのサイトでは、行列累乗よりも計算量の良いアルゴリズムが使われています。
これを持っているとより高みを目指せるかもしれないです。

解法4 幻のO(1)解法

https://twitter.com/noimi_kyopro/status/1281947146757926912

はまやんはまやんはまやん

hamayanhamayan's blog

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