最近のAtCoder Problemsのアップデートで昔の問題がお勧めに出てくるようになりました。誰も解説書いてなかったので（多分）書きます。
atcoder.jp
問題
直線状に
匹のぽよくんが存在している。
番目のぽよくんは
から
の範囲のマスを自由に移動できる。ぽよくんが添え字の順にそれぞれ異なるマスにいるとき何通りの配置があるかを
で割った値を求めよ。
制約
のとき
解説
まずわかりやすくするために
として移動できる区間の左端にそろえておく。また、一番初めの要素として
などを入れておくと処理が簡単になる。
・
番目のぽよをマス
に配置したときの通り数
としてdpを行う。このままdpを行うと遷移のパターンが
通りあるため制限時間に収めることができない。しかし、マスにぽよを配置できるときマス
にもぽよを配置しても問題ないことがわかる。よって配置可能な左端のマスを持ってそこに足していき、累積和の要領でそれ以降のマス目に足せばよい。
時間計算量は
自分の提出
atcoder.jp
