Submission #99341


Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

ll K,N;

vi mult(vi v,vi w){
	vi res(2*K,0);
	rep(i,K)rep(j,K){
		res[i+j]+=v[i]*w[j]%MOD;
	}
	for(int i=2*K-1;i>=K;i--)rep2(j,i-K,i){
		res[j]=(res[j]+res[i])%MOD;
	}
	return res;
}

vi f(ll N){
	vi res(2*K,0);
	if(N<K){
		res[N]=1;
		return res;
	}
	vi v=f(N/2);
	res=mult(v,v);
	if(N&1)res=mult(res,f(1));
	return res;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>K>>N;
	N--;
	vi res=f(N);
	ll ans=0;
	rep(i,K)ans+=res[i];
	cout<<ans%MOD<<endl;
}

Submission Info

Submission Time
Task T - フィボナッチ
User evima
Language C++ (G++ 4.6.4)
Score 8
Code Size 1661 Byte
Status AC
Exec Time 318 ms
Memory 1300 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 318 ms 1300 KB
01 AC 166 ms 1112 KB
02 AC 268 ms 1244 KB
03 AC 75 ms 980 KB
04 AC 26 ms 864 KB
90 AC 24 ms 920 KB
91 AC 24 ms 868 KB