結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー 木村晃
提出日時 2023-01-15 17:16:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,788 bytes
コンパイル時間 1,531 ms
コンパイル使用メモリ 165,812 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-29 05:46:52
合計ジャッジ時間 2,153 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main(){
      | ^~~~

ソースコード

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];
//                 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]%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;

// }

ll fibm(ll n,ll m){
	//0,1,1,1をn乗して2番目を返す
	//一般の行列累乗は面倒だったのでadhoc
	ll aa=0,bb=1,cc=1,dd=1;
	ll a=1,b=0,c=0,d=1;
	ll ta,tb,tc,td;
	while(n){
		if(n%2){
			ta=aa*a+bb*c;
			tb=aa*b+bb*d;
			tc=cc*a+dd*c;
			td=cc*b+dd*d;
			a=ta%m;b=tb%m;c=tc%m;d=td%m;
		}
		ta=aa*aa+bb*cc;
		tb=aa*bb+bb*dd;
		tc=cc*aa+dd*cc;
		td=cc*bb+dd*dd;
		aa=ta%m;bb=tb%m;cc=tc%m;dd=td%m;
		n/=2;
	}
	return b;
}

ll n,m;
main(){
	scanf("%d%d",&n,&m);
	printf("%d",fibm(n-1,m));
}
0