Typical DP Contest F - 準急
解法
駅で止まるような駅までのパターン数、のようにしていきたいところですが、連続して何駅止まったか、という情報が必要になるので無理です。
逆転の発想をして、駅を通過するような駅~のパターン数、としましょう。
ダミーの駅というものが存在し、ここを必ず通過している、と仮定します。初期状態では、、そしてです。
駅で通過するには、駅を通過している、駅にはとまるが駅で通過している、駅と駅にはとまるが駅で通過している…駅から駅にはとまるが駅で通過している、というパターンがあります。
結局はこのようになります。
これは、累積和なりを用いることで、簡単に計算することができます。
あとは、答えを求めるだけです。
駅にはとまらなければならないので、駅を通過している、駅を通過してそれ以降とまる、駅を通過してそれ以降とまる、…駅を通過してそれ以降とまる、というパターンの総和になります。ここで、駅はとまる必要があるので、先ほどと条件が少しことなることに注意してください。
ということで、答えは以下のようになります。
あとは、で割った余りをとることに注意しつつ計算していけばよいです。