結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0