Submission #227817


Source Code Expand

#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;


typedef deque<int> di;

const int mod = inf + 7;
int K, N;

inline void advance(di &co){
	int n = co.size();
	co.push_front(0);
	rep(i, n) (co[i] += co[n]) %= mod;
	co.pop_back();
}

inline void dbl(di &v){
	
	int n = v.size();
	di prev = v;
	v.clear();
	v.resize(n * 2);
	
	rep(i, n) rep(j, n) (v[i + j] += (ll)prev[i] * prev[j] % mod) %= mod;
	
	di co(K, 1);
	for(int i = n; i < 2 * n; i++){
		
		rep(j, n) (v[j] += (ll)v[i] * co[j] % mod) %= mod;
		advance(co);
	}
	rep(i, n) v.pop_back();
}


int main(){
	cin >> K >> N;
	N--;
	
	di v(K, 0);
	v[1] = 1;
	
	int p;
	for(p = 31; !(N >> p & 1); p--);
	p--;
	for(; p >= 0; p--){
		dbl(v);
		if(N >> p & 1) advance(v);
	}
	
	ll ans = 0;
	rep(i, K) ans += v[i];
	cout << ans % mod << endl;
	
	return 0;
}

Submission Info

Submission Time
Task T - フィボナッチ
User nadeko
Language C++ (G++ 4.6.4)
Score 8
Code Size 1263 Byte
Status AC
Exec Time 929 ms
Memory 1208 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 929 ms 1132 KB
01 AC 527 ms 1168 KB
02 AC 918 ms 1084 KB
03 AC 166 ms 996 KB
04 AC 275 ms 1208 KB
90 AC 29 ms 976 KB
91 AC 28 ms 1068 KB