AtCoder Regular Contest 160 D - Mahjong
メモ
以下の二つの操作を使って作れる、長さNで総和がMの数列Aは何通りあるか
・長さKの区間に1を足す
・あるAiの値をK足す
この問題の難しさは、異なる操作によって同じ数列が作られる事があるという点にある
これは、数えあげpdfのgreedyからの帰着のように考え
任意の数列Aについて、それに対応する操作列というものを一意に対応付け(つまり単射)ればいい
こういう時は判定問題を考える
Aを作れるかという判定は、Aiに縦向きに1つ置く操作は、iを左端として横向きにK個置く操作の上位互換であるため
左から貪欲に縦においておける。
すると各iについて横向きの操作(以後これを操作Yと呼び、縦向きの操作を操作Xとよぶ)の回数と操作Xの操作回数が一意に定まる
そしてこの一対一関係を崩さないように、X, Yの操作列を数え上げれば
それが数列Aとしてあり得る場合の数になる。
ここでは各iについて、操作YをK回以上使わなければいい
Xiの操作回数、Yiの操作回数の合計がM/Kになるようにしたうえで
ほう助原理でYをK回以上使う場所が何か所あるか
というので解ける