Submission #5890707

---

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] += 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 Info

Judge Result