提出 #18349711


ソースコード 拡げる

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;
}

提出情報

提出日時
問題 T - フィボナッチ
ユーザ ransewhale
言語 C++ (GCC 9.2.1)
得点 8
コード長 1528 Byte
結果 AC
実行時間 100 ms
メモリ 12152 KB

コンパイルエラー

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

ジャッジ結果

セット名 All
得点 / 配点 8 / 8
結果
AC × 7
セット名 テストケース
All 00, 01, 02, 03, 04, 90, 91
ケース名 結果 実行時間 メモリ
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