第一回日本最強プログラマー学生選手権予選 F. Candy Retribution
これ1000点じゃないだろ
問題概要
解法
条件を満たす昇順の列 に対して、それを並べる方法は通りある。 ここでは にが個含まれることを指す。
よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているものの並べ方の総数」とした時、それをFPSで表わすなら
として
となる。 さて、ここに「M番目とM+1番目の値が同一」という条件を追加する。当然これは扱いづらいので、余事象を考えることにする。 すなわち、
ここで、はに関するFPS のの含まれる項の係数を全て取り出し、に関するFPSを作る操作を指す。つまり、具体的な式として書けば
である。さて上記の余事象の式を変形していくと
となる。欲しいのは と上記の式の 項目から項目。 を掛けて累積和を取っておけば、項と項の2項を得るだけでよく、上記式をよくにらめば愚直に計算しても調和級数になっているから計算できて、解ける。
これは何?笑