結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー chocorusk
提出日時 2018-07-27 23:27:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,629 bytes
コンパイル時間 679 ms
コンパイル使用メモリ 81,048 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-05 05:16:58
合計ジャッジ時間 1,356 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define MOD 1000000007LL

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;

long long int powmod(long long int a, long long int k, long long int m){
	if(a==0){
		return 0;
	}
	long long int apow[35];
	for(int i=0; i<35; i++){
		if(i==0){
			apow[i]=a;
		}else{
			apow[i]=apow[i-1]*apow[i-1]%m;
		}
	}
	long long int ans=1;
	for(int i=34; i>=0; i--){
		if(k>=(1ll<<i)){
			ans=ans*apow[i]%m;
			k-=(1ll<<i);
		}
	}
	return ans;
}
 
ll inv(ll x, ll p){
  return powmod(x, p-2, p);
}

P pow5(ll a, ll b, ll k){
	ll ap[35], bp[35];
	for(int i=0; i<35; i++){
		if(i==0){
			ap[i]=a, bp[i]=b;
		}else{
			ap[i]=(ap[i-1]*ap[i-1]%MOD+5*bp[i-1]*bp[i-1]%MOD)%MOD;
			bp[i]=2*ap[i-1]*bp[i-1]%MOD;
		}
	}
	ll a0=1, b0=0;
	for(int i=34; i>=0; i--){
		if(k>=(1ll<<i)){
			ll a1=a0;
			a0=(a0*ap[i]%MOD+5*b0*bp[i]%MOD)%MOD;
			b0=(a1*bp[i]+b0*ap[i])%MOD;
			k-=(1ll<<i);
		}
	}
	return P(a0, b0);
}

P inv5(ll a, ll b){
	ll t=(a*a%MOD-5*b*b%MOD+MOD)%MOD;
	t=inv(t, MOD);
	ll a1=a*t%MOD, b1=(MOD-b*t%MOD)%MOD;
	return P(a1, b1);
}

P mul(ll a1, ll a2, ll b1, ll b2){
	ll a=(a1*b1%MOD+5*a2*b2%MOD)%MOD, b=(a1*b2+a2*b1)%MOD;
	return P(a, b);
}

int main()
{
	ll n;
	cin>>n;
	ll iv2=500000004;
	P p1=pow5(iv2, iv2, n), p2=pow5(iv2, MOD-iv2, n);
	ll f1=(p1.second-p2.second+MOD)%MOD;
	P p3=pow5(iv2, iv2, n+1), p4=pow5(iv2, MOD-iv2, n+1);
	ll f2=(p3.second-p4.second+MOD)%MOD;
	cout<<f1*f2%MOD<<endl;
	return 0;
}
0