結果

問題 No.147 試験監督（2）
ユーザー maine_honzukimaine_honzuki
提出日時 2020-05-24 23:45:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 551 ms / 2,000 ms
コード長 5,390 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 175,040 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-10-12 12:21:31
合計ジャッジ時間 4,515 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const long long mod = 1e9 + 7;

template <uint MD>
struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
    friend istream& operator>>(istream& is, M& r) { return is >> r.v; }
};
using Mint = ModInt<mod>;

template <class T>
struct Matrix {
    vector<vector<T>> A;
    Matrix() {}
    Matrix(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}
    Matrix(size_t n) : A(n, vector<T>(n, 0)){};
    size_t height() const { return (A.size()); }
    size_t width() const { return (A[0].size()); }
    inline const vector<T>& operator[](int k) const { return (A.at(k)); }
    inline vector<T>& operator[](int k) { return (A.at(k)); }
    static Matrix I(size_t n) {
        Matrix mat(n);
        for (int i = 0; i < n; i++)
            mat[i][i] = 1;
        return (mat);
    }
    Matrix& operator+=(const Matrix& B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }
    Matrix& operator-=(const Matrix& B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }
    Matrix& operator*=(const Matrix& B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector<vector<T>> C(n, vector<T>(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }
    Matrix& operator^=(long long k) {
        Matrix B = Matrix::I(height());
        while (k > 0) {
            if (k & 1)
                B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }
    Matrix operator+(const Matrix& B) const {
        return (Matrix(*this) += B);
    }
    Matrix operator-(const Matrix& B) const {
        return (Matrix(*this) -= B);
    }
    Matrix operator*(const Matrix& B) const {
        return (Matrix(*this) *= B);
    }
    Matrix operator^(const long long k) const {
        return (Matrix(*this) ^= k);
    }
    friend ostream& operator<<(ostream& os, Matrix& p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }
    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0)
                    idx = j;
            }
            if (idx == -1)
                return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};


int main() {
    int N;
    cin >> N;

    Mint ans = 1;
    while (N--) {
        long long C;
        long long D = 0;
        string D_str;
        cin >> C >> D_str;

        for (int i = 0; i < D_str.size(); i++) {
            int d = D_str[i] - '0';
            D *= 10;
            D += d;
            D %= (mod - 1);
        }

        using Mat = Matrix<Mint>;
        Mat mat(2);
        mat[0][0] = 1;
        mat[0][1] = 1;
        mat[1][0] = 1;
        mat[1][1] = 0;

        mat ^= C;
        ans *= (mat[0][0] + mat[1][0]).pow(D + mod - 1);
    }

    cout << ans << endl;
}
0