Submission #627930

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    const int MOD = (int)1e9 + 7;

    static int CalcNaive(int n, int k) {
       var dp = new int[n+1, k]; // [駅, 連続して停止した駅数]

       dp[1, 1] = 1;
       for (int i = 2; i <= n; i++) { // i 番目の駅

           // i 番目の駅で停車する
           for (int j = 0; j < k-1; j++) {
               dp[i, j+1] = (dp[i, j+1] + dp[i-1, j]) % MOD;
           }

           // i 番目の駅で停車しない
           for (int j = 0; j < k; j++) {
               dp[i, 0] = (dp[i, 0] + dp[i-1, j]) % MOD;
           }
       }

       int ans = 0;
       for (int i = 1; i < k; i++) {
           ans = (ans + dp[n, i]) % MOD;
       }

       return ans;
    }

    static void Main() {
        var nk = ReadInts();
        int n = nk[0], k = nk[1];

        Console.WriteLine(CalcNaive(n, k));

    }
}

Submission Info

Judge Result