結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー chocoruskchocorusk
提出日時 2018-07-27 23:22:13
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,852 bytes
コンパイル時間 579 ms
コンパイル使用メモリ 79,192 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 05:07:51
合計ジャッジ時間 1,447 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, m;
	cin>>n>>m;
	ll iv2=500000004;
	P p1=pow5(iv2, iv2, m), p2=pow5(iv2, MOD-iv2, m);
	ll a1=p1.first, a2=p1.second, b1=p2.first, b2=p2.second;
	P p3=inv5(a1-1, a2), p4=inv5(b1-1, b2);
	P p5=pow5(a1, a2, n), p6=pow5(b1, b2, n);
	P p7=mul(a1, a2, p3.first, p3.second), p8=mul(b1, b2, p4.first, p4.second);
	P p9=mul(p7.first, p7.second, p5.first-1, p5.second), p10=mul(p8.first, p8.second, p6.first-1, p6.second);
	cout<<(p9.second-p10.second+MOD)%MOD<<endl;
	return 0;
}
0