結果

問題 No.147 試験監督（2）
コンテスト
ユーザー なお
提出日時 2015-02-09 00:47:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 433 ms / 2,000 ms
コード長 2,209 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 172,224 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 10:24:36
合計ジャッジ時間 3,877 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
const int MOD = int(1e9+7);

int N,M,W,H;

template<class _Tc>
class Matrix {
private:
    unsigned int r, c;
    vector<vector<_Tc> > v;
public:
    Matrix(unsigned int rows, unsigned int columns) : r(rows),c(columns){
        v.resize(rows);
        for(unsigned int i = 0; i < rows; ++i) v[i].resize(columns);
    }
    vector<_Tc> &operator [](unsigned int row){ return v[row]; }
    const Matrix &operator *=(const Matrix &m){
        if(c != m.r) throw;
        Matrix n(r,m.c);
        for(unsigned int i = 0; i < r; ++i)
            for(unsigned int j = 0; j < m.c; ++j)
                for(unsigned int k = 0; k < c; ++k)
                    n.v[i][j] = (n.v[i][j] + v[i][k] * m.v[k][j] % MOD) % MOD;
        return *this=n;
    }
    static const Matrix unit(unsigned int s, _Tc v = 1){
        Matrix n(s,s);
        for(unsigned int i = 0; i < s; ++i) n.v[i][i] = v;
        return n;
    }
    const Matrix pow(ll p) const {
        if(c != r) throw;
        Matrix n = Matrix::unit(r), m = *this;
        while(p > 0){
            if(p & 1) n *= m;
            m *= m;
            p >>= 1;
        }
        return n;
    }
};


ll in(){
    ll r=0;
    string s; cin >> s;
    int l = s.size();
    REP(i,l) r = (r*10+(s[i] - '0'))%(MOD-1);
    return r;
}

ll dp[10010][2];

long long fib(ll n){
    Matrix<long long> a(2,2);
    a[0][0] = a[0][1] = a[1][0] = 1; a[1][1] = 0;
    a = a.pow(n);
    return a[1][0];
}

int binpow(ull x, ull k, int m){
    if(x==0) return 0;
    if(k==0) return 1;
    if(k%2==0) return binpow(((x%m)*(x%m))%m, k/2, m);
    else return ((x%m)*binpow(x, k-1, m)) % m;
}

int main(){
    do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0);
    cin >> N;
    ll c, d, res = 1;
    REP(i,N){
        cin >> c;
        d = in();
        res = binpow(fib(c+2), d, MOD) % MOD * res % MOD;
    }

    cout << res << endl;
    return 0;
}
0