結果

問題 No.147 試験監督（2）
ユーザー kagasankagasan
提出日時 2019-12-10 20:40:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,633 bytes
コンパイル時間 1,690 ms
コンパイル使用メモリ 170,032 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 02:16:30
合計ジャッジ時間 3,297 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

ll pls(ll a, ll b){return (a + b) % MOD;}
ll mlt(ll a, ll b){return (a * b) % MOD;}

class mat{
    public:
    ll A, B, C, D;
    mat(ll a, ll b, ll c, ll d){
        A = a; B = b;
        C = c; D = d;
    }
    mat(mat x, mat y){
        A = pls(mlt(x.A, y.A), mlt(x.B, y.C));
        B = pls(mlt(x.A, y.B), mlt(x.B, y.D));
        C = pls(mlt(x.C, y.A), mlt(x.D, y.C));
        D = pls(mlt(x.C, y.B), mlt(x.D, y.D));
    }
};

ll f(ll b){
    mat m(1, 1, 1, 0);
    mat ret(1, 0, 0, 1);
    while(b > 0){
        if(b & 1)ret = mat(ret, m);
        m = mat(m, m);
        b >>= 1;
    }
    return pls(ret.A, ret.B);
}

ll md(string s){
    ll ret = 0;
    rep(i, s.size()){
        ret = (ret * 10 + s[i] - '0') % MOD;
    }
    return ret;
}

ll m_pow(ll a, ll b){
    ll ret = 1;
    while(b > 0){
        if(b & 1)(ret *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return ret;
}

int main(){

    ll ans = 1;
    ll N;
    cin >> N;
    rep(i, N){
        ll c;
        cin >> c;
        string d;
        cin >> d;
        ans = mlt(ans, m_pow(f(c), md(d)));
    }
    cout << ans << endl;

    return 0;
}
0