結果

問題 No.147 試験監督（2）
コンテスト
ユーザー kagasan
提出日時 2019-12-10 20:24:17
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,682 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,622 ms
コンパイル使用メモリ 168,020 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-24 02:12:57
合計ジャッジ時間 3,070 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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));
    }
    void add(mat x){
        A = pls(A, x.A);
        B = pls(B, x.B);
        C = pls(C, x.C);
        D = pls(D, x.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;
}

int main(){

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

    return 0;
}
0