結果

問題 No.147 試験監督（2）
コンテスト
ユーザー srjywrdnprkt
提出日時 2022-12-24 11:29:53
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 554 ms / 2,000 ms
コード長 2,462 bytes
コンパイル時間 1,391 ms
コンパイル使用メモリ 147,312 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-18 05:08:21
合計ジャッジ時間 4,351 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <numeric>
#include <deque>
#include <complex>
#include <cassert>

using namespace std;

const long long modc = 1e9+7;

template<typename T>
struct Kitamasa{
    vector<T> a; //initial values (a_0, ..., a_K-1)
    vector<T> c; //coefficients (c_0, ..., c_K-1)
    int K; //size

    Kitamasa(vector<T> & _a, vector<T>& _c) : a(_a), c(_c), K((int) _a.size()){
        for (int i=0; i<K; i++){
            a[i] %= modc;
            c[i] %= modc;
        }
    }

    //calculate {x_0, ..., x_N}
    vector<T> dfs(long long N){
        assert(N >= K);

        if (N == K) return c;
        vector<T> res(K);
        if (N & 1 || N < K*2){
            vector<T> x = dfs(N-1);
            for (int i=0; i<K; i++) res[i] = (c[i] * x[K-1]) % modc;
            for (int i=1; i<K; i++) res[i] = (res[i] + x[i-1]) % modc;
        }
        else{
            vector<vector<T>> x(K, vector<T>(K));
            x[0] = dfs(N>>1);
            for (int i=1; i<K; i++){
                for (int j=0; j<K; j++) x[i][j] = (c[j] * x[i-1][K-1]) % modc;
                for (int j=1; j<K; j++) x[i][j] = (x[i][j] + x[i-1][j-1]) % modc;
            }
            for (int i=0; i<K; i++){
                for (int j=0; j<K; j++){
                    res[j] += (x[0][i] * x[i][j]) % modc;
                    res[j] %= modc;
                }
            }
        }

        return res;
    }

    //calculate a_N
    T calc (long long N){
        if (N < K) return a[N];
        vector<T> x = dfs(N);
        T res = 0;
        for (int i=0; i<K; i++) res = (res + (x[i] * a[i]) % modc) % modc;
        return res;
    }

};

long long mod_exp(long long b, long long e){
    if (b == 0) return 0;
    long long ans = 1;
    b %= modc;

    while (e > 0){
        if ((e & 1LL)) ans = (ans * b) % modc;
        e = e >> 1LL;
        b = (b*b) % modc;
    }

    return ans;
}

long long div(string &D){
    long long res = 0;
    for (int i=0; i<D.size(); i++) res = ((res * 10) % (modc-1) + D[i]-'0') % (modc-1);
    return res;
}

int main(){

    long long N, C, ans=1;
    string D;
    vector<long long> a = {1, 2}, c = {1, 1};
    Kitamasa K(a, c);
    cin >> N;

    for (int i=0; i<N; i++){
        cin >> C >> D;
        ans *= mod_exp(K.calc(C), div(D));
        ans %= modc;
    }

    cout << ans << endl;

    return 0;
}
0