Submission #5890512
Source Code Expand
using System; using System.Linq;//リストの使用 using System.Collections.Generic; using System.Text;//テキストの高速出力に必要 class Program { static void Main() { string[] input = Console.ReadLine().Split(' '); int k = int.Parse(input[0]); long n = long.Parse(input[1]); long mod = 1000000007; long[] coe = new long[k]; long[] fir = new long[k]; for(int i = 0; i < k; i++) { coe[i] = 1; fir[i] = 1; } Console.WriteLine(FormulaTerm(coe,fir,n-1,mod)); } static long FormulaTerm(long[] coe, long[] fir, long k, long p) {//漸化式a_n = a_n + a_n-1+…の係数coe、初項for=(a_0,a_1,…)として、第k項(k=1でa_1)(mod p)を求める int n = coe.Length; if(k < fir.Length) { return fir[k]%p;//求める項が初項の時 } for(int i = 0; i < n; i++) { coe[i] %= p; fir[i] %= p; } List<long> multipleList = new List<long>();//0で1たす、1で2倍 while(k > 0) { if(k % 2 == 1) { multipleList.Add(0); k--; }else { multipleList.Add(1); k /= 2; } //Console.WriteLine(k); } int m = multipleList.Count(); long[] backCoe = new long[n]; backCoe[n-1] = 1; long[] nextCoe = new long[n]; long[,] subCoe = new long[n,n]; for(int mul = m-1; mul >= 0; mul--) { if(multipleList[mul] == 0) { k++; if(k >= n) { for(int i = 0; i < n-1; i++) { nextCoe[i] += backCoe[i+1]; nextCoe[i] %= p; nextCoe[i] += coe[i]; nextCoe[i] %= p; } nextCoe[n-1] += coe[n-1]; nextCoe[n-1] %= p; }else nextCoe[n-1-k] = 1; } else { k *= 2; if(k >= n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i == 0) subCoe[i,j] = backCoe[i]; else subCoe[i,j] = 0; } } for(int i = 0; i < n-1; i++) { for(int j = 0; j < n-1; j++) { subCoe[i+1,j] += subCoe[i,j+1]; subCoe[i+1,j] %= p; subCoe[i+1,j] += coe[j]; subCoe[i+1,j] %= p; } subCoe[i+1,n-1] += coe[n-1]; subCoe[i+1,n-1] %= p; } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { nextCoe[j] += backCoe[n-1-i]*subCoe[i,j]; nextCoe[j] %= p; } } }else nextCoe[n-1-k] = 1; } for(int i = 0; i < n; i++) { backCoe[i] = nextCoe[i]; nextCoe[i] = 0; } //Console.WriteLine(string.Join(" ", backCoe)); } long answer = 0; for(int i = 0; i < n; i++) { answer += fir[i]*backCoe[n-1-i]; answer %= p; //Console.WriteLine(backCoe[i]); } return answer; } }
Submission Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | suikameron |
Language | C# (Mono 4.6.2.0) |
Score | 0 |
Code Size | 3178 Byte |
Status | WA |
Exec Time | 1120 ms |
Memory | 16992 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 8 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | WA | 1120 ms | 16992 KB |
01 | WA | 637 ms | 13920 KB |
02 | WA | 1116 ms | 16992 KB |
03 | WA | 212 ms | 10336 KB |
04 | AC | 21 ms | 9276 KB |
90 | WA | 23 ms | 11348 KB |
91 | WA | 23 ms | 9300 KB |