結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー dai
提出日時 2023-11-09 14:51:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 7,230 bytes
コンパイル時間 2,231 ms
コンパイル使用メモリ 205,804 KB
最終ジャッジ日時 2025-02-17 20:11:36
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,l,r)for(int i=(l);i<(r);i++)
#define rrep(i,l,r)for(int i=(l);i>=(r);i--)
#define erep(i,l,r)for(int i=(l);i<=(r);i++)
#define lrep(i,l,r)for(ll i=(l);i<(r);i++)
#define lrrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define lerep(i,l,r)for(ll i=(l);i<=(r);i++)
#define ALL(a)(a).begin(),(a).end()
#define rALL(a)(a).rbegin(),(a).rend()
#define FI first
#define SE second
#define PB push_back
#define intmax 2147483646
#define lmax 9223372036854775806
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<long long, int>;
using pll = pair<long long, long long>;
using pivi = pair<int, vector<int>>;
const ld PI = 3.1415926535897932;
// (Max) int: 10^9 ll: 10^18 ull: 10^19

template<typename T> struct Edge{
    int to; T w;
    Edge(int to_, T w_=1){
        to = to_;
        w=w_;
    }
};
template<typename T> using Tree = vector<vector<Edge<T>>>;
template<typename T> using Graph = vector<vector<Edge<T>>>;

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         rotate(k,itr2,last);
         return true;
      }
   }
   rotate(first,k,last);
   return false;
}

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

//べき乗 mod
ll modpow(ll a, ll n, ll mod){ ll res = 1; while(n > 0){ if(n & 1) res = res * a % mod; a = a * a % mod;n >>= 1;} return res;}

//逆元 mod (a^-1)
ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod);
}

//nCr mod (need COMinit())
const ll MAX = 3000000;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
ll fac[MAX], finv[MAX], inv[MAX];

void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    rep(i,2,MAX){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll COM(ll n, ll k){
    if(n < k) return(0);
    if(n < 0 || k < 0) return(0);
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

struct RollingHash {
private:
    using ull = unsigned long long;
    static const ull _mod = 0x1fffffffffffffff;
    static ull _base;
    vector<ull> _hashed, _power;

    inline ull _mul(ull a, ull b) const {
        ull au = a >> 31;
        ull ad = a & ((1UL << 31) - 1);
        ull bu = b >> 31;
        ull bd = b & ((1UL << 31) - 1);
        ull mid = ad * bu + au * bd;
        ull midu = mid >> 30;
        ull midd = mid & ((1UL << 30) - 1);
        ull ans = au * bu * 2 + midu + (midd << 31) + ad * bd;
        
        ans = (ans >> 61) + (ans & _mod);
        if (ans >= _mod) ans -= _mod;
        return ans;
    }
public:
    RollingHash(const string &s) {
        ll n = s.size();
        _hashed.assign(n + 1, 0);
        _power.assign(n + 1, 0);
        _power[0] = 1;
        for(ll i = 0; i < n; i++) {
            _power[i + 1] = _mul(_power[i], _base);
            _hashed[i + 1] = _mul(_hashed[i], _base) + s[i];
            if(_hashed[i + 1] >= _mod) _hashed[i + 1] -= _mod;
        }
    }
    
    // l番目からr番目の前までのhashを取得
    ull get(ll l, ll r) const {
        ull ret = _hashed[r] + _mod - _mul(_hashed[l], _power[r - l]);
        if(ret >= _mod) ret -= _mod;
        return ret;
    }
    
    // h1(hash1) と h2(hash2) の連結 (h2len : length of h2)
    ull connect(ull h1, ull h2, ll h2len) const {
        ull ret = _mul(h1, _power[h2len]) + h2;
        if(ret >= _mod) ret -= _mod;
        return ret;
    }
    
    void connect(const string &s) {
        ll n = _hashed.size() - 1, m = s.size();
        _hashed.resize(n + m + 1);
        _power.resize(n + m + 1);
        for(ll i = n; i < n + m; i++) {
            _power[i + 1] = _mul(_power[i], _base);
            _hashed[i + 1] = _mul(_hashed[i], _base) + s[i - n];
            if(_hashed[i + 1] >= _mod) _hashed[i + 1] -= _mod;
        }
    }
    
    ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) const {
        ll len = min(r1 - l1, r2 - l2);
        ll low = -1, high = len + 1;
        while(high - low > 1) {
            ll mid = (low + high) / 2;
            if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};
mt19937_64 mt{(unsigned int)time(NULL)};
RollingHash::ull RollingHash::_base = mt() % RollingHash::_mod;

vector<ll> Z_algo(string S){
    vector<ll> Z(S.size());
    Z[0] = S.size();
    int i = 1, j = 0;
    while(i < S.size()){
        while(i + j < S.size() && S[j] == S[i + j]) j++;
        Z[i] = j;

        if(j == 0){
            i++;
            continue;
        }
        int k = 1;
        while(k < j && k + Z[k] < j){
            Z[i + k] = Z[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return(Z);
}

ll mod;

//mat_multi
vector<vector<ll>> mat_mul(vector<vector<ll>> &a, vector<vector<ll>> &b){
    vector<vector<ll>> res(a.size(), vector<ll>(b[0].size()));
    lrep(i,0,a.size()){
        lrep(j,0,b[0].size()){
            lrep(k,0,b.size()){
                (res[i][j] += a[i][k] * b[k][j]) %= mod;
            }
        }
    }
    return(res);
}

//mat_pow
vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll n){
    vector<vector<ll>> res(a.size(), vector<ll>(a.size()));
    lrep(i,0,a.size()){
        res[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) res = mat_mul(a, res);
        a = mat_mul(a, a);
        n >>= 1;
    }
    return res;
}

//--------------------------------------

int main(){
    ll N, M;
    cin >> N >> M;
    mod = M;
    vector<vector<ll>> mat(2, vector<ll>(2));
    mat[0] = {1, 1};
    mat[1] = {1, 0};
    mat = mat_pow(mat, N-1);
    cout << mat[1][0] << endl;
}
0