結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー 木村晃
提出日時 2023-01-15 17:11:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,141 bytes
コンパイル時間 1,761 ms
コンパイル使用メモリ 175,232 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-29 05:40:50
合計ジャッジ時間 4,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
using vi=vector<int>;
using vll=vector<ll>;
using vii=vector<vector<int>>;
using pii=pair<int,int>;
using vvpii=vector<vector<pair<int,int>>>;
#define all(x) x.begin(),x.end()
#define rep0(i,a) for(int i=0;i<a;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repll(i,a,b) for(ll i=a;i<b;i++)
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {a = b;return true;}return false;}
// const long long inf = 1LL<<60;
const int INF = (1<<30);
// const int MOD=1000000007;
// const int MOD=10000000007;

template<typename T>
struct Kitamasa{
    vector<T> a;    // 初期値ベクトル
    vector<T> d;    // 係数ベクトル
    int k;
    ll M;
    
    Kitamasa(vector<T>& a, vector<T>& d,ll M) : a(a), d(d), k((int)a.size()) {}
    
    // a_n の係数ベクトルを求める
    vector<T> dfs(int64_t n){
        if(n == k)  return d;
        
        vector<T> res(k);
        if(n & 1 || n < k * 2){
            vector<T> x = dfs(n - 1);
            for(int i = 0; i < k; ++i)  res[i] = d[i]*x[k - 1]%M;
            for(int i = 0; i + 1 < k; ++i)  res[i + 1] += x[i]%M;
        }
        else{
            vector<vector<T>> x(k, vector<T>(k));
            x[0] = dfs(n >> 1);
            for(int i = 0; i + 1 < k; ++i){
                for(int j = 0; j < k; ++j)  x[i + 1][j] = d[j] * x[i][k - 1]%M;
                for(int j = 0; j + 1 < k; ++j)  x[i + 1][j + 1] += x[i][j]%M;
            }
            for(int i = 0; i < k; ++i){
                for(int j = 0; j < k; ++j){
                    res[j] += x[0][i] * x[i][j]%M;
                }
            }
        }

        return res;
    }

    // a_n を求める。nは0-index
    T calc(int64_t n){
        vector<T> x = dfs(n);
        T res = 0;
        for(int i = 0; i < k; ++i)  res += x[i] * a[i]%M;
        return res;
    }
};

int main(){
  ll N,M;
  cin>>N>>M;
  N--;
  vll a={0,1};
  vll d={1,1};
  Kitamasa<ll> k(a,d,M);

  int t_res=k.calc(N);
  t_res%=M;
  cout<<t_res<<endl;

}
0