結果

問題 No.147 試験監督（2）
ユーザー codershifthcodershifth
提出日時 2016-01-13 00:49:49
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 2,234 bytes
コンパイル時間 1,513 ms
コンパイル使用メモリ 175,424 KB
実行使用メモリ 203,704 KB
最終ジャッジ日時 2024-09-19 18:54:40
合計ジャッジ時間 8,728 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

const ll Mod = (int)(1E+9)+7;
class Invigilator2 {
public:
    // f(x,k) = x^(10^k)
    //        = x^(10^(k-1)*10)
    //        = x^(10^(k-1)) * ... * x^(10^(k-1))
    //
    map<int,ll> pow_;
    ll myPow(ll a, string k) {
        if (a == 0LL)
            return 1LL;

        reverse(RANGE(k));

        ll ret = 1LL;
        ll prev = a;// a^(10^(k-1))
        for (auto c : k)
        {
            ll cur = 1LL;
            ll ten = 1LL;

            REP(i,c-'0')
                (cur *= prev) %= Mod;
            (ret *= cur) %= Mod;
            REP(i,10)
                (ten *= prev) %= Mod;
            prev = ten;
        }
        return ret;
    }
    void solve(void) {
        int N;
        cin>>N;
        vector<ll> C(N);
        vector<string> D(N);
        REP(i,N)
        {
            cin>>C[i]>>D[i];
        }

        map<ll,ll> memo;

        function<ll(ll)> calc = [&](ll d)
        {
            if (memo.count(d))
                return memo[d];
            if (d <= 0LL)
                return 1LL;
            if (d == 1LL)
                return 2LL;
            if (d == 2LL)
                return 3LL;
            if (d == 3LL)
            {
                return 5LL;
            }
            ll left = d/2;
            ll right = d - left;

            ll ret = 0LL;
            // left+1 番目を空席にする
            if (left >= 0 && right-1 >= 0)
                (ret += (calc(left) * calc(right-1)) % Mod) %= Mod;
            // left+1 番目を空席にしない
            if (left-1 >= 0 && right-2 >= 0)
                (ret += (calc(left-1) * calc(right-2)) % Mod) %= Mod;
            return memo[d] = ret;
        };
        ll cnt = 1LL;
        REP(i,N)
        {
            (cnt *= myPow(calc(C[i]), D[i])) %= Mod;
        }
        cout<<cnt<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new Invigilator2();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0