結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0