Submission #5411035

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var K = line[1];

            if (K == 2)
            {
                var dp2 = new int[N, 2];
                dp2[0, 1] = 1;
                for (int i = 0; i < N - 1; i++)
                {
                    dp2[i + 1, 0] = dp2[i, 0] + dp2[i, 1];
                    dp2[i + 1, 1] = dp2[i, 0];
                }
                return dp2[N - 1, 1];
            }

            var dp = new int[N];
            dp[0] = 1;
            for (int i = 0; i < K - 2; i++)
            {
                dp[i + 1] = dp[i] * 2 % mod;
            }

            for (int i = K - 2; i < N - 2; i++)
            {
                dp[i + 1] = (2 * dp[i] - dp[i - (K - 2)]) % mod;
            }

            return (dp[N - 2] - dp[N - 2 - (K - 2)]) % mod;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Submission Info

Judge Result