Submission #5411049
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])%mod; dp2[i + 1, 1] = dp2[i, 0] % mod; } 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
Submission Time | |
---|---|
Task | F - 準急 |
User | kzrnm |
Language | C# (Mono 4.6.2.0) |
Score | 0 |
Code Size | 2842 Byte |
Status | WA |
Exec Time | 41 ms |
Memory | 18912 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 4 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 41 ms | 18912 KB |
01 | AC | 34 ms | 14944 KB |
02 | WA | 28 ms | 10848 KB |
03 | WA | 27 ms | 11360 KB |
04 | WA | 33 ms | 12640 KB |
90 | AC | 23 ms | 11348 KB |
91 | AC | 23 ms | 9300 KB |