Submission #99009


Source Code Expand

#include <algorithm>
#include <cmath>
#include <climits>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <stack>
#include <utility>
#include <vector>
using namespace std;


typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define REP(i,n) for(int i=0;i<(int)n;i++) 
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) 
#define ALL(c) (c).begin(),(c).end() 

LL MOD = 1000000007; 
const int MAXN = 1001;
LL A[MAXN];
LL CO[MAXN];
LL temp[2*MAXN];
LL m2[MAXN][MAXN];
//m :Aの長さ
//n レベル
LL solve(LL n ,int m) {
  if(m==1) {
    LL ret = A[0];
    LL mul = CO[0];
    for(;n>0;n>>=1) {
      if((n&1)==1) {
	ret = (ret*mul)%MOD;
      }
      mul = (mul*mul) % MOD;
      
    }
    return ret;
  }
  for(int j=0; j<m; j++)
    m2[0][j] = CO[j];
  for(int i=1; i<m-1; i++) {
    for(int j=0; j<m; j++) {
      LL x = m2[i-1][m-1] * CO[j];
      if(j-1>=0) x += m2[i-1][j-1];
      m2[i][j] = x% MOD;
      
    }
  }
  
  LL ret[MAXN];
  for(int i=0; i<m; i++) ret[i] = 0;
  ret[0]=1;
  
  for(int l=32; l>=0; l--) {
    if((n>>l)&1) {
      //      cout<<l<<endl;
      for(int i=0; i<m; i++) temp[i] = ret[m-1] * CO[i];
      for(int i=1; i<m; i++) temp[i] += ret[i-1];
      for(int i=0; i<m; i++) ret[i] = temp[i] % MOD;
      /*      cout<<"hjoge"<<endl;
      for(int i=0; i<m; i++) cout<<ret[i]<<" ";
      cout<<endl;*/
    }
    if(l>0) {
      for(int i=0; i<2*m; i++) temp[i] = 0;
      for(int i=0; i<m; i++) {
	for(int j=0; j<m; j++) {
	  temp[i+j] += ret[i] * ret[j] % MOD;
	}
      }
      for(int i=0; i<2*m-2; i++)
	temp[i] %= MOD;
      /*    cout<<"temp"<<endl;
      for(int i=0; i<2*m-1; i++)
	cout<<temp[i]<<" ";
	cout<<endl;*/
      for(int i=0; i<m ;i++) {
	LL s = temp[i];
	for(int j=m; j<2*m-1; j++)
	  s += temp[j] * m2[j-m][i] % MOD;
	ret[i] =s % MOD;
      }
      /*
      cout<<l<<endl;
      for(int i=0; i<m; i++)
	cout<<ret[i] <<" ";
	cout<<endl;*/
    }
  }
  LL s =0;
  for(int i=0; i<m; i++) {
    s += ret[i] * A[i] % MOD;
    //    cout<<ret[i]<<" ";
  }
  //  cout<<endl;
  return s % MOD;
}

int main() {
  LL K,N;
  cin>>K>>N;

  for(int i=0; i<K; i++) A[i] = 1;
  for(int i=0; i<K; i++) CO[i] = 1;
  
  LL ans = solve(N-1,K);
  cout<<ans<<endl;
  
  return 0;
}

Submission Info

Submission Time
Task T - フィボナッチ
User tokoharu
Language C++ (G++ 4.6.4)
Score 8
Code Size 2495 Byte
Status AC
Exec Time 1645 ms
Memory 8876 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 1630 ms 8744 KB
01 AC 1005 ms 7128 KB
02 AC 1645 ms 8876 KB
03 AC 220 ms 3620 KB
04 AC 1610 ms 8680 KB
90 AC 30 ms 1036 KB
91 AC 23 ms 1040 KB