yukicoder No.1191 数え上げを愛したい（数列編）

• 問題
• AC

条件を満たす数列のすべての要素は互いに異なるので、昇順のものだけ数えて後で$N!$を掛ければよい。

$S_1$が与えられたとき、残りの項は

$f(k) :=$ $1$回の操作で$A$マス以上進むとして、$N-1$回操作してちょうど$k$マス進む場合の数

と考えると形としては$f(A)+f(A+1)+...+f(B)$通りのように求まる。（実際には$S_1+k \le M$であるような$f(k)$までしか足せない）したがって、$f$かあるいはその累積和$F(k) = \sum_{i=1}^kf(i)$が求めれば$S_1 = 1, 2, ..., N$について足せばよいことになる。形式的べき級数で考えると

$$\begin{aligned} f(k) & = [x^k](x^A+x^{A+1}...)^{N-1} \\ & =[x^k]\Bigl(\frac{x^A}{1-x}\Bigr)^{N-1} \\ & =[x^{k-A(N-1)}](1-x)^{-(N-1)} \\ & = [x^{k-A(N-1)}] \sum_{i=0}^\infty \binom{i+N-2}{N-2}x^i\\ & = \binom{k-A(N-1)+N-2}{N-2} \end{aligned}$$

$F(k)$を求めるなら、$(1-x)^{-1}$をもう一つ掛けることになるので$\binom{k-A(N-1)+N-1}{N-1}$となる。