No.023 C

連続している読めない部分ごとに組み合わせの数を計算し, それの総乗が答えとなる.

連続している読めない部分を $A_i, A_{i+1}, \dots, A_{i+k-1}$ とすると, この組み合わせの数は $A_{i+k}-A_i$ の玉と $k$ 個の仕切りを並べる組み合わせの数に等しいので, $d = A_{i+k}-A_i$ とすると ${}_{d+k}C_k$ となる.

$k \leq 2000$ なので,

$${}_{d+k}C_k = \frac{(d+k)(d+k-1)\dots(d+1)}{k(k-1)\dots 1}$$

で計算できる. 割り算は逆元を使う.