AGC036 C - GP 2 - ツバサの備忘録

解法

まず、最終的な数列の中に奇数が $p$ 個存在するときについて考えます。 $p$ は最大で $min(m,n)$ となります。
すると、残った $x_{j}$ に1加算する操作を2つまとめて、 $x_{i}$ に2加算する操作 $(m-p)/2$ 回分に置き換えることができます(もちろん、残った回数が奇数の際は端数が発生するので、考慮せずスルーします)。
すると、 $p$ 個の奇数を選ぶのは、 $_{N}C_{p}$ で求めることができます。そして、 $x_{i}$ に2加算する操作 $m + (m-p)/2$ 回を $N$ 個の数字に割り振るのは、 $_{m + (m-p)/2}H_{N} = _{m + (m-p)/2 + N -1}C_{N-1}$ で求めることができます。
基本的にはこれでよいのですが、いくつか実現不可能なパターンが存在します。 $i \neq j$ の制限があるためです。
これは主に2つのパターンがあります。数列のどこか1つが $2M+1$ 以上の奇数パターンと、 $2(M+1)$ 以上の偶数パターンです。どちらのパターンも、そのような数字が同時に2個以上出現することはありません(全体の総和が $3M$ にしかならないからです)。

$2M+1$ 以上の奇数パターン
仮に $x_{0}$ がその値だったと仮定して、最後に $N$ 倍してあげることで網羅できます。 $x_{0}$ が奇数なので、それ以外に $p-1$ 個の奇数が存在するはずです。この割り振り方は、 $_{n-1}C_{p-1}$ 通りです。
そして、2を加算する操作は、 $(m-p)/2$ 回だけ残っています(少なくとも $M$ 回は $x_{0}$ に割り振らなければなりませんが、それ以外はどこに割り振ってもいいです)。よって、割り振り方は $_{(m-p)/2}H_{N}$ 通りとなります。
$2(M+1)$ 以上の偶数パターン
1つめのパターンと同様に考えると、奇数の割り振りは $_{n-1}C_{p}$ となります。
2を加算する操作の割り振りは、 $_{(m-p)/2-1}H_{N}$ となります。今回は、 $x_{0}$ に少なくとも $M+1$ 回割り振る必要があるので、残る回数は $(m-p)/2 - 1$ 回です。

あとは、最初に計算した全体から、実現不可能なパターンを引けばよいです。
$_{N}C_{p} \times _{m + (m-p)/2}H_{N} - N ( _{n-1}C_{p-1} \times _{(m-p)/2}H_{N} - _{n-1}C_{p} \times _{(m-p)/2-1}H_{N})$
となります。
これを全ての $p$ に対して計算を行い、総和を求めれば答えとなります。

感想

奇数の個数を決め打ちして、2に加算する回数にまとめてしまう、という考え方が天から降ってきました(わーい)。
実現できないコーナーケースを見つけて、冷静に対処できたのも良かったです。