Submission #627960

---

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; j++) {
               dp[i, 0] = (dp[i, 0] + dp[i-1, j]) % MOD;
           }

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

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

    static int Calc(int n, int k) {
        var dp = new int[n+1]; // i 番目の駅で停車しない

        var q = new Queue<int>(); // 連続して停止した駅の数 (q.Count < K)
        q.Enqueue(1);
        int qsum = q.Sum();
        for (int i = 2; i < n; i++) {
            // i 番目の駅で停車しない
            dp[i] = (dp[i] + dp[i-1]) % MOD; // i-1 から停車せずに i に来る
            dp[i] = (dp[i] + qsum) % MOD;    // 連続して 1~K-1 回停車して i に来る

            // i 番目の駅で停車する
            q.Enqueue(dp[i-1]); // i 番目の駅(0 回連続停車)
            qsum = (qsum + dp[i-1]) % MOD;
            if (q.Count == k) {
                qsum = (qsum - q.Dequeue() + MOD) % MOD;
            }
        }

        int ans = dp[n-1]; // n-1 番目の駅まで 0 回連続停車
        ans = (ans + qsum) % MOD; // n-1 番目の駅まで 1~K-1 回連続停車
        if (q.Count == k-1) { // k-1 回連続停車を取り除く
            ans = (ans - q.Peek() + MOD) % MOD;
        }
        return ans;
    }

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

        Console.WriteLine(Calc(n, k));
    }
}

Submission Info

Judge Result