beet's soil

競プロのことなど

Japan Alumni Group Summer Camp 2017 Day 1 C - すごろく

まともな解説記事が見つからなかったので書く

このままやると添え字が無限にバグるのでひっくり返す、つまりm-1スタートで0に行くようにする

b_i >=0 のときがやばくて、DP配列を一つでやるとつらい

DP1_i := マスiからスタートしたときの期待値
DP2_i := そのマスにサイコロを振って移動して来たときの期待値
とすると、
b_i>=0 のとき DP2_i = DP1_{i-B_i}
b_i < 0 のとき DP2_i = DP1_i - B_i
で、遷移は
DP1_i = (sum{j=0}^{N-1} DP2_{i - A_j} + 1) / N
みたいになる

遷移が畳み込みっぽく書けそうなので変形する C_i = num(A_j == i) とする

DP1_i = (sum{j=0}^{M-1} DP2_{i-j} * C_j + 1) / N
と変形できる

あとは分割統治FFTしておわり 分割統治の各状態において、[0, L)は全部求まっているのでうれしい
注意点として、各段ではCの長さを適切にしないとTLEするんだけど、短すぎるの(R-M)はダメで、R-Lくらいは必要っぽい