Typical DP Contest

Submission #5890707

Source codeソースコード

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] += backCoe[0]*coe[i];
            nextCoe[i] %= p;
          }
          nextCoe[n-1] += backCoe[0]*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[j];
              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] += subCoe[i,0]*coe[j];
              subCoe[i+1,j] %= p;
            }
            subCoe[i+1,n-1] += subCoe[i,0]*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;
            }
            //Console.WriteLine(i+"i"+subCoe[i,0]+" "+subCoe[i,1]);
          }
        }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;
    }
    return answer;
  }
}

Submission

Task問題 T - フィボナッチ
User nameユーザ名 suikameron
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 AC
Score得点 8
Source lengthソースコード長 3253 Byte
File nameファイル名
Exec time実行時間 1161 ms
Memory usageメモリ使用量 19040 KB

Test case

Set

Set name Score得点 / Max score Cases
All 8 / 8 00,01,02,03,04,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 1161 ms 19040 KB
01 AC 665 ms 15968 KB
02 AC 1159 ms 16992 KB
03 AC 218 ms 12384 KB
04 AC 21 ms 9404 KB
90 AC 23 ms 11348 KB
91 AC 22 ms 9300 KB