Submission #5411369
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];
var dp = new int[N, 2];
dp[0, 1] = 1;
for (int i = 1; i < K - 1; i++)
{
dp[i, 0] = dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 1]) % mod;
}
{
int i = K - 1;
dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1]) % mod;
dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 1] - 1) % mod;
}
for (int i = K; i < N; i++)
{
dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1]) % mod;
dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 1] - dp[i - K, 0]) % mod;
if (dp[i, 1] < 0)
dp[i, 1] += mod;
}
return dp[N - 1, 1];
}
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
Submission Time |
|
Task |
F - 準急 |
User |
kzrnm |
Language |
C# (Mono 4.6.2.0) |
Score |
4 |
Code Size |
2815 Byte |
Status |
AC |
Exec Time |
50 ms |
Memory |
18912 KB |
Judge Result
Set Name |
All |
Score / Max Score |
4 / 4 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
49 ms |
18912 KB |
01 |
AC |
37 ms |
16864 KB |
02 |
AC |
35 ms |
12512 KB |
03 |
AC |
34 ms |
15584 KB |
04 |
AC |
50 ms |
18272 KB |
90 |
AC |
24 ms |
13268 KB |
91 |
AC |
23 ms |
9172 KB |