結果

問題 No.147 試験監督（2）
コンテスト
ユーザー codershifth
提出日時 2016-01-13 00:49:49
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

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