結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー chocorusk
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0