結果

問題 No.147 試験監督（2）
ユーザー kagasankagasan
提出日時 2019-12-10 22:37:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,961 bytes
コンパイル時間 1,552 ms
コンパイル使用メモリ 166,308 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 07:40:56
合計ジャッジ時間 3,983 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 2 ms
4,376 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;
}

ll m_pow(ll a, string b){
    ll ret = 1;
    ll p[11];
    p[0] = 1;
    p[1] = a;
    for(ll i = 2; i <= 10; i++)p[i] = (p[i - 1] * p[1]) % MOD;
    rrep(i, b.size()){
        ll c = b[i] - '0';
        ret *= p[c];
        p[1] = p[10];
        for(ll i = 2; i <= 10; i++)p[i] = (p[i - 1] * p[1]) % MOD;
    }
    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), d));
    }
    cout << ans << endl;

    return 0;
}
0