位置は0-indexedで考える.

位置 \(i\) まで到達する経路の数を \(C(i)\) とすると,

\[C(i) = \sum_{j=1}^m C(i-x_j)\]

となる. これをDPで計算すれば普通は計算できる. しかし, \(10^{17}+7\) の余りを保持するためには long を使わなければならず, \(8n\) バイトは約 \(160\) Mバイトなので MLE となる.

そこで, まずは \(10^{17}+7 = 17 \times 9920467 \times 592951213\) であることを利用する. \(17 \times 9920467 = 168647939\) および \(592951213\) はそれぞれ int で収まるので, これらの数値を法として計算し, 中国剰余定理を用いることで \(10^{17}+7\) を法とした解を得ることができる. これでメモリ使用量を半分にできる.

次に, \(m = \lceil n/2 \rceil\) として, \(i \leq m\) から \(i+x \geq m+1\) にジャンプする経路の組み合わせ数を考える. これは \(0 \rightarrow i\) の経路の数と \(i+x \rightarrow n-1\) の経路の数の積である. \(0 \rightarrow i\) の経路の数は当然 \(C(i)\) であり, \(i+x \rightarrow n-1\) の経路の数は \(C(n-1-(i+x))\) になるので, この経路の数は \(C(i)C(n-1-(i+x))\) となる. よって, \(C(m)\) までの値のみを保存すればいいので, さらにメモリ使用量を半分にすることができ, MLE を回避できる.