Submission #18349711


Source Code Expand

Copy
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int k;
ll x[1111],y[1111][1111],tmp[1111];

void add_one(ll *f){
	int i;
	std::fill(tmp,tmp+k,f[k-1]);
	tmp[0] = f[k-1];
	for(i=1; i<k; ++i){
		add_mod(tmp[i],f[i-1]);
	}
	for(i=0; i<k; ++i){
		f[i] = tmp[i];
	}
}

void dbl(void){
	int i,j;
	for(i=0; i<k; ++i){
		y[0][i] = x[i];
	}
	for(i=1; i<k; ++i){
		for(j=0; j<k; ++j){
			y[i][j] = y[i-1][j];
		}
		add_one(y[i]);
	}
	std::fill(tmp,tmp+k,0ll);
	for(i=0; i<k; ++i){
		for(j=0; j<k; ++j){
			add_mod(tmp[j],x[i]*y[i][j]%MOD);
		}
	}
	for(i=0; i<k; ++i){
		x[i] = tmp[i];
	}
}

int main(void){
	int i,r,j;
	bool flag = false;
	ll q=0ll,n,ans = 0ll;
	std::cin >> k; r = k;
	std::fill(x,x+k,1ll);
	std::cin >> n; --n;
	if(n<k){
		std::cout << 1 << std::endl;
		return 0;
	}
	for(i=40; i>=0; --i){
		q *= 2;
		if(flag){
			dbl();
		}
		if(n&(1ll<<i)){
			++q;
			if(flag){
				add_one(x);
			}
		}
		if(q>=r && (!flag)){
			flag = true;
			while(q>r){
				add_one(x); ++r;
			}
		}
	}
	for(i=0; i<k; ++i){
		add_mod(ans,x[i]);
	}
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Submission Time
Task T - フィボナッチ
User ransewhale
Language C++ (GCC 9.2.1)
Score 8
Code Size 1528 Byte
Status AC
Exec Time 100 ms
Memory 12152 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:10: warning: unused variable ‘j’ [-Wunused-variable]
   65 |  int i,r,j;
      |          ^

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 100 ms 12152 KB
01 AC 62 ms 10292 KB
02 AC 96 ms 12040 KB
03 AC 29 ms 6212 KB
04 AC 6 ms 3448 KB
90 AC 2 ms 3508 KB
91 AC 2 ms 3464 KB