AGC036-C GP 2 - kaage精進録

問題リンク

細部が詰められなかったので解説の方法でACしてしまったが、あとで落ち着いて詰め直したらできた。自分の解法は解説の方法より（実装は面倒だが）直感的だと思うので、紹介しておく。

問題概要

長さ $N$ の数列があって、異なる2要素を選んでそれぞれ1と2を足す、という操作を $M$ 回行う。操作のあとの数列としてありうるものは何通りあるか、 $\bmod 998244353$ で求めよ。

考察

DPで通せそうな制約でもないので、必要条件・十分条件を列挙して数え上げを考える。次の3つが必要十分条件となる。

数列の総和が $3M$ であること
数列の最大値が $2M$ 以下であること
数列のうち、奇数は $M$ 個以下であること

証明は省くが、やってみると明らかそうなので本番なら無証明で通せそうな感じはある。

さて、これを満たす数列を数え上げるわけだが、解説では次のように行っていた。

奇数が $x$ 個の場合、まず最大値を考えないと $_{N}C_x\cdot{}_{\frac{3M-x}{2}}H_N$ 個ある。

ここからある要素が $2M$ を超えるものを除きたいが、総和を考えればこのような要素は高々ひとつなので、このような要素の場所を固定すれば、総和 $M$ , 長さ $N$ で、その要素が $0$ を超えるような数列の数と対応する。このような数列の数は、前と同じ問題を $N$ と $N-1$ について解いて差をとれば求まるので、この問題が解けた。

この解法は実装が簡単だが、発想がちょっと難しい。（と自分は思った。）

自分の考えた解法は次のようである。

$1$ と $2$ の塊が複数個あり、これを振り分けていくという発想をする。 $1$ の塊は当然 $0$ 個以上 $M$ 個以下であり、 $M$ と偶奇は一致する。ここで、 $1$ の塊の数を $x$ 個とおく。

まず、 $2M$ の要素を含むか含まないかで場合分けをする。

$2M$ を含む場合、残りの $N-1$ 個から集合を選んでそれに $1$ を足し、残った $2$ の塊を適当に振り分ける、という操作だと考えると、このような通り数は $N\cdot{}_{N-1}C_x\cdot{}_{\frac{M-x}{2}}H_N$ となる。

$2M$ を含まない場合、 $2$ の塊の振り分け方 ${}_{\frac{3M-x}{2}}H_N$ 個から、 $2M$ 以上の要素を含む場合を除き、 $1$ の塊の振り分け方 $_N C_x$ を掛ければよい。

$2M$ 以上の要素を含む場合の数は、1要素固定すれば $N\sum_{i=0}^{\frac{m-x}{2}}{}_i H_{n-1}$ 通りだとわかるので、累積和などを用いて高速化でき、この問題が解けた。