結果

問題 No.147 試験監督（2）
ユーザー mayoko_mayoko_
提出日時 2015-04-04 16:36:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 516 ms / 2,000 ms
コード長 3,676 bytes
コンパイル時間 1,395 ms
コンパイル使用メモリ 166,628 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-07-04 01:57:14
合計ジャッジ時間 4,043 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int MM = MOD-1;

//typedef double number;
//const number eps = 1e-8;
typedef long long number;
typedef vector<number> vec;
typedef vector<vec> matrix;

// O( n )
matrix identity(int n) {
    matrix A(n, vec(n));
    for (int i = 0; i < n; ++i) A[i][i] = 1;
    return A;
}
// O( n )
number inner_product(const vec &a, const vec &b) {
    number ans = 0;
    for (int i = 0; i < a.size(); ++i)
        ans += a[i] * b[i];
    return ans;
}
// O( n^2 )
vec mul(const matrix &A, const vec &x) {
    vec y(A.size());
    for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < A[0].size(); ++j)
            y[i] = A[i][j] * x[j];
    return y;
}
// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
    matrix C(A.size(), vec(B[0].size()));
    for (int i = 0; i < C.size(); ++i)
        for (int j = 0; j < C[i].size(); ++j)
            for (int k = 0; k < A[i].size(); ++k) {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= MOD;
            }
    return C;
}
// O( n^3 log e )
matrix pow(const matrix &A, ll e) {
    if (e == 0) return identity(A.size());
    if (e == 1) return A;
    if (e % 2 == 0) {
        matrix tmp = pow(A, e/2);
        return mul(tmp, tmp);
    } else {
        matrix tmp = pow(A, e-1);
        return mul(A, tmp);
    }
}
// O( n^3 )
//number det(matrix A) {
//    const int n = A.size();
//    number D = 1;
//    for (int i = 0; i < n; ++i) {
//        int pivot = i;
//        for (int j = i+1; j < n; ++j)
//            if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
//        swap(A[pivot], A[i]);
//        D *= A[i][i] * (i != pivot ? -1 : 1);
//        if (abs(A[i][i]) < eps) break;
//        for(int j = i+1; j < n; ++j)
//            for(int k = n-1; k >= i; --k)
//                A[j][k] -= A[i][k] * A[j][i] / A[i][i];
//    }
//    return D;
//}
// O(n)
number tr(const matrix &A) {
    number ans = 0;
    for (int i = 0; i < A.size(); ++i)
        ans += A[i][i];
    return ans;
}
// O( n^3 ).
//int rank(matrix A) {
//    const int n = A.size(), m = A[0].size();
//    int r = 0;
//    for (int i = 0; r < n && i < m; ++i) {
//        int pivot = r;
//        for (int j = r+1; j < n; ++j)
//            if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
//        swap(A[pivot], A[r]);
//        if (abs(A[r][i]) < eps) continue;
//        for (int k = m-1; k >= i; --k)
//            A[r][k] /= A[r][i];
//        for(int j = r+1; j < n; ++j)
//            for(int k = i; k < m; ++k)
//                A[j][k] -= A[r][k] * A[j][i];
//        ++r;
//    }
//    return r;
//}
ll getMod(const string& s) {
    int n = s.size();
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans *= 10;
        ans += (s[i]-'0');
        ans %= MM;
    }
    return ans;
}
// x^p
ll powmod(ll x, ll p, ll m = MOD) {
    if (x == 0) return 0;
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p % 2 == 0) {
        ll tmp = powmod(x, p/2, m);
        return (tmp*tmp)%m;
    } else {
        ll tmp = powmod(x, p-1, m);
        return (tmp*x)%m;
    }
}

int main() {
    int N;
    cin >> N;
    ll ans = 1;
    matrix A(2, vector<number>(2));
    A[0][1] = A[1][0] = A[1][1] = 1;
    while (N--) {
        ll C;
        string D;
        cin >> C >> D;
        ll d = getMod(D);
        matrix B = pow(A, C-1);
        ll tmp = B[1][0] + B[1][1]*2;
        tmp %= MOD;
        ans *= powmod(tmp, d);
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
0