結果

問題 No.534 フィボナッチフィボナッチ数
コンテスト
ユーザー 王源成
提出日時 2025-12-21 20:47:52
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 886 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,613 ms
コンパイル使用メモリ 195,372 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-21 20:48:01
合計ジャッジ時間 2,770 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int M;
struct node{
    int a[2][2];
    node operator * (const node b) const{
        node c={0,0,0,0}; 
        for(int k=0;k<2;k++)
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                     c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%M)%M;
        return c;
    }
}s,b;
node qpow(node x,int y){
    if(y==1) return x;
    node z=qpow(x,y/2);
    if(y%2) return z*z*x;
    return z*z;
}
int n,ans=0;
 
signed main(){
    //freopen("fib.in","r",stdin);
    //freopen("fib.out","w",stdout);
    b={1,1,1,0};
    s={1,0,0,0};
    cin>>n;
    ans=0;M=2e9+16; 
    if(n==0) ans=0;
    else if(n==1) ans=1;
    else ans=(s*qpow(b,n-1)).a[0][0];
    n=ans;
    ans=0;M=1e9+7;
    if(n==0) ans=0;
    else if(n==1) ans=1;
    else ans=(s*qpow(b,n-1)).a[0][0];
    cout<<ans<<'\n';
    return 0; 
}
0