結果

問題 No.147 試験監督（2）
コンテスト
ユーザー mayoko_
提出日時 2015-02-09 14:18:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 232 ms / 2,000 ms
コード長 2,097 bytes
コンパイル時間 1,456 ms
コンパイル使用メモリ 159,908 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-06-23 16:09:00
合計ジャッジ時間 3,022 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <bits/stdc++.h>

#define INF 1000000000

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll mod10[210];
void init() {
    mod10[0] = 1;
    for (int i = 1; i < 210; i++) {
        mod10[i] = (mod10[i-1]*10) % (MOD-1);
    }
}

class Mat {
public:
    ll a, b, c, d;
};

Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    C.a = ((A.a * B.a) % MOD + (A.b * B.c) % MOD) % MOD;
    C.b = ((A.a * B.b) % MOD + (A.b * B.d) % MOD) % MOD;
    C.c = ((A.c * B.a) % MOD + (A.d * B.c) % MOD) % MOD;
    C.d = ((A.c * B.b) % MOD + (A.d * B.d) % MOD) % MOD;
    return C;
}

Mat modMul(const Mat& A, const ll p) {
    if (p == 0) {
        Mat E;
        E.a = 1; E.b = 0, E.c = 0; E.d = 1;
        return E;
    }
    if (p == 1) {
        return A;
    }
    if (p % 2 == 0) {
        const Mat B = modMul(A, p/2);
        return mul(B, B);
    }
    const Mat B = modMul(A, p-1);
    return mul(A, B);
}

ll modpow(ll a, ll n) {
    if (a == 0) return 0;
    if (n == 0) return 1;
    if (n == 1) return a;
    if (n % 2 == 0) {
        ll tmp = modpow(a, n/2);
        return (tmp * tmp) % MOD;
    }
    ll tmp = modpow(a, n-1);
    return (tmp * a) % MOD;
}

int main(void) {
    init();
    int N;
    cin >> N;
    ll ans = 1;
    while (N--) {
        ll C;
        string D;
        cin >> C >> D;
        int len = D.size();
        ll d = 0;
        for (int i = 0; i < len; i++) {
            d += (mod10[len-i-1] * (D[i]-'0')) % (MOD-1);
            d %= (MOD-1);
        }
        Mat A;
        A.a = 0; A.b = 1; A.c = 1; A.d = 1;
        A = modMul(A, C-1);
//        cout << A.a << "\t" << A.b << endl;
//        cout << A.c << "\t" << A.d << endl;
        ll tmp = (A.c + 2LL * A.d) % MOD;
        ll p = modpow(tmp, d);
        ans *= p;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
0