結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
![]() |
提出日時 | 2025-10-08 13:21:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 9,080 bytes |
コンパイル時間 | 2,968 ms |
コンパイル使用メモリ | 231,584 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-08 13:21:36 |
合計ジャッジ時間 | 4,093 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using vi = vector<int>; using vvi = vector<vector<int>>; using vvvi = vector<vector<vector<int>>>; using vll = vector<ll>; using vvll = vector<vector<ll>>; using vvvll = vector<vector<vector<ll>>>; using vd = vector<double>; using vvd = vector<vector<double>>; using vstr = vector<string>; using vchar = vector<char>; using vvchar = vector<vector<char>>; using vb = vector<bool>; using vvb = vector<vector<bool>>; using vvvb = vector<vector<vector<bool>>>; using pii = pair<int,int>; using pll = pair<long long, long long>; using Graph = vector<vector<int>>; using WeightedGraph = vector<vector<pair<int,int>>>; const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1}; #define rep(i, a, b) for(int i = (int)a; i < (int)b; i++) #define REP(i, a, b) for (int i = (int)a; i <= (int)b; i++) #define rrep(i, a, b) for(int i = (int)b-1; i >= (int)a; i--) #define RREP(i, a, b) for(int i = (int)b; i >= (int)a; i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define YESNO(flag) cout << (flag ? "Yes" : "No") << "\n" #define spa " " const int inf = 1070000000; const long long INF = 4500000000000000000; const long long MOD = 998244353; //const long long MOD = 1000000007; const double pi = 3.141592653589793238; const double eps = (1e-10); const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string abc = "abcdefghijklmnopqrstuvwxyz"; 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; } //xのn乗 ll llpow(ll x, ll n) { ll ans = 1; while(n > 0) { if(n & 1) ans *= x; x *= x; n >>= 1; } return ans; } ll modpow(ll x, ll n, ll mod) { ll ans = 1; while(n > 0) { if(n & 1) ans = ans * x % mod; x = x * x % mod; n >>= 1; } return ans; } //mod pでのaの逆元 ll inverse(ll a, ll p) { return modpow(a, p-2, p); } //nの階乗 ll fact(ll n) { if(n == 0) return 1; else return n * fact(n-1); } ll modfact(ll n, ll mod) { if(n == 0) return 1; else return (n * modfact(n-1, mod)) % mod; } //nCr=n!/r!(n-r)! mod p ll comb(ll n, ll r, ll mod) { ll a = modfact(n, mod), b = modfact(r, mod), c = modfact(n-r, mod); b = inverse(b, mod); c = inverse(c, mod); return (((a*b)%mod)*c)%mod; } //1+2+...+n = n(n+1)/2 ll triangle(ll n) { ll x = n*(n+1); return x/2; } //素数判定 bool is_prime(long long x) { if(x == 1) return false; for(long long i = 2; i*i <= x; i++) { if(x % i == 0) return false; } return true; } //エラトステネスの篩 vll sieve(ll N) { vb P(N+1, true); P[0] = false; P[1] = false; for(ll i = 2; i*i <= N; i++) { for(ll j = 2; j < N/i; j++) { P[i*j] = false; } } vll A(0); REP(i,2,N) { if(P[i]) A.push_back(i); } return A; } //座標圧縮 vector<int> compress(vector<int> A) { vector<int> B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); vector<int> res(A.size()); for(int i = 0; i < (int)A.size(); i++) { res[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin(); } return res; } //正方形グリッドの右回転, 左回転 void rotate_right(vector<vector<char>> &S) { int N = S.size(); auto T = S; rep(i,0,N) rep(j,0,N) { T[i][j] = S[N-1-j][i]; } S = T; } void rotate_left(vector<vector<char>> &S) { int N = S.size(); auto T = S; rep(i,0,N) rep(j,0,N) { T[i][j] = S[j][N-1-i]; } S = T; } //2点(a,b)と(x,y)の距離 long double dist(pair<long double, long double> a, pair<long double, long double> b) { return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second)); } long double man(pair<long double, long double> a, pair<long double, long double> b) { return abs(a.first-b.first) + abs(a.second-b.second); } //内分点 pair<long double, long double> internal_division(pair<long double, long double> a, pair<long double, long double> b, long double p) { long double x = a.first + (b.first - a.first) * p; long double y = a.second + (b.second - a.second) * p; return {x, y}; } //桁数 int digit(ll N) { if(N <= 9) return 1; return 1 + digit(N / 10); } //A進数文字列NをB進数に変換. A,Bは10以下 string base_change(string N, ll A, ll B) { ll X = stoll(N), Y = 0; ll i = 1; while(X != 0) { Y += (X % 10) * i; i *= A; X /= 10; } X = Y, Y = 0; i = 1; while(X != 0) { Y += (X % B) * i; i *= 10; X /= B; } return to_string(Y); } //回文判定 bool palin(string S) { rep(i,0,S.size()) { if(S[i] != S[S.size()-1-i]) return false; } return true; } //hh:mm:ss to second int convert_to_time(string S) { ll h = 10*(S[0]-'0') + (S[1]-'0'); ll m = 10*(S[3]-'0') + (S[4]-'0'); ll s = 10*(S[6]-'0') + (S[7]-'0'); return h*3600+m*60+s; } //DFS void dfs(const Graph &G, int v, vector<bool> &seen) { seen[v] = true; for (auto next_v : G[v]) { if (!seen[next_v]) { dfs(G, next_v, seen); } } } void griddfs(const vector<vector<char>> &G, int x, int y, vector<vector<bool>> &seen) { int H = G.size(), W = G[0].size(); seen[x][y] = true; for (int i = 0; i < 8; i++) { int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 or nx >= H or ny < 0 or ny >= W) continue; if (!seen[nx][ny] and G[nx][ny] != '#') griddfs(G, nx, ny, seen); } } //BFS void bfs(const Graph &G, int v, vector<int> &dist) { rep(i,0,dist.size()) dist[i] = inf; dist[v] = 0; queue<int> q; q.push(v); while(!q.empty()) { int u = q.front(); q.pop(); for(auto next_u : G[u]) { if(dist[next_u] == inf) { dist[next_u] = dist[u] + 1; q.push(next_u); } } } } void gridbfs(const vector<vector<char>> &G, int x, int y, vector<vector<int>> &dist) { int H = G.size(), W = G[0].size(); dist[x][y] = 0; queue<pair<int, int>> q; q.push(make_pair(x, y)); while(!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for(int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 or nx >= H or ny < 0 or ny >= W) continue; if(dist[nx][ny] == inf and G[nx][ny] != '#') { dist[nx][ny] = dist[x][y] + 1; q.push(make_pair(nx, ny)); } } } } //ワーシャル・フロイド vector<vector<ll>> floyd(vector<vector<ll>> G) { int N = G.size(); auto dp = G; for (int k = 0; k < N; k++){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if(dp[i][j] > dp[i][k] + dp[k][j] and dp[i][k] != INF and dp[k][j] != INF) { dp[i][j] = dp[i][k] + dp[k][j]; } } } } return dp; } //Union-Find struct UnionFind { vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2 UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化 for(int i = 0; i < N; i++) par[i] = i; } int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根} if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { // xとyの木を併合 int rx = root(x); //xの根をrx int ry = root(y); //yの根をry if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける } bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す int rx = root(x); int ry = root(y); return rx == ry; } }; void solve() { } ll N, M; vvll matrix_product(vvll A, vvll B) { int H = A.size(), W = A[0].size(), S = B.size(), T = B[0].size(); if(W != S) { cout << "matrix_size_error" << "\n"; return vvll(0); } vvll C(H, vll(T, 0)); rep(i,0,H) rep(j,0,T) { rep(k,0,W) { C[i][j] += A[i][k]*B[k][j]; C[i][j] %= M; } } return C; } vvll matrix_pow(vvll A, ll n) { int N = A.size(); vvll ans(N, vll(N, 0)); rep(i,0,N) ans[i][i] = 1; while(n > 0) { if(n & 1) ans = matrix_product(ans, A); A = matrix_product(A, A); n >>= 1; } return ans; } int main(){ cin >> N >> M; vvll A = {{0,1},{1,1}}; cout << matrix_pow(A, N-1)[0][1] << "\n"; return 0; }