結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー 木村晃木村晃
提出日時 2023-01-15 17:05:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,115 bytes
コンパイル時間 1,703 ms
コンパイル使用メモリ 173,844 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-09 04:53:04
合計ジャッジ時間 2,448 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
    
    Kitamasa(vector<T>& a, vector<T>& d) : 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];
            for(int i = 0; i + 1 < k; ++i)  res[i + 1] += x[i];
        }
        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];
                for(int j = 0; j + 1 < k; ++j)  x[i + 1][j + 1] += x[i][j];
            }
            for(int i = 0; i < k; ++i){
                for(int j = 0; j < k; ++j){
                    res[j] += x[0][i] * x[i][j];
                }
            }
        }

        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];
        return res;
    }
};

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

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

}
0