結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー ichyoichyo
提出日時 2015-05-22 22:49:35
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 316 ms / 3,000 ms
コード長 2,752 bytes
コンパイル時間 1,471 ms
コンパイル使用メモリ 171,708 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-07-06 05:21:30
合計ジャッジ時間 2,420 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

class range {
    struct Iterator {
        int val, inc;
        int operator*() {return val;}
        bool operator!=(Iterator& rhs) {return val < rhs.val;}
        void operator++() {val += inc;}
    };
    Iterator i, n;
    public:
    range(int e) : i({0, 1}), n({e, 1}) {}
    range(int b, int e) : i({b, 1}), n({e, 1}) {}
    range(int b, int e, int inc) : i({b, inc}), n({e, inc}) {}
    Iterator& begin() {return i;}
    Iterator& end() {return n;}
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}
vector<int> res;
void dfs(int P, int LP, int C, int LC, int A) {
    const int a[] = {2,3,5,7,11,13};
    const int b[] = {4,6,8,9,10,12};
    if(P > 0) {
        REP(i, 6) if(LP <= i) dfs(P-1, i, C, 0, A + a[i]);
    } else if(C > 0) {
        REP(i, 6) if(LC <= i) dfs(P, 0, C-1, i, A + b[i]);
    } else {
        res.push_back(A);
    }
}
typedef vector<LL> Array;
typedef vector<Array> Matrix;

const int MOD = 1e9 + 7;

// 行列の掛け算 O(N * M * S)
Matrix mul(const Matrix& a, const Matrix& b){
    int N = a.size(), M = b[0].size(), S = a[0].size();
    assert(S == b.size());
    Matrix c(N, Array(M));
    REP(i, N) REP(k, S) REP(j, M) {
        c[i][j] += a[i][k] * b[k][j];
        c[i][j] %= MOD;
    }
    return c;
}
// 正方行列の累乗 O(N^3 * logn)
Matrix pow(Matrix a, LL b){
    int N = a.size();
    Matrix c(N, Array(N));
    REP(i, N) c[i][i] = 1;
    while(b > 0){
        if(b & 1) c = mul(c, a);
        a = mul(a, a);
        b >>= 1;
    }
    return c;
}


int main(){
    iostream_init();
    LL n;
    while(cin >> n) {
        res.clear();

        int P, C;
        cin >> P >> C;
        dfs(P, 0, C, 0, 0);
        int K = *max_element(res.begin(), res.end());
        vector<int> dp(K);
        for(int x : res) dp[x-1]++;

        Matrix M(K, Array(K));
        for(int i = 0; i < K; i++) {
            M[0][i] = dp[i];
        }
        for(int i = 1; i < K; i++) {
            M[i][i-1] = 1;
        }

        vector<LL> ps(K);
        M = pow(M, n-1);
        REP(i, ps.size()){
            ps[i] = M[i][0];
        }

        LL ans = 0;
        REP(i, ps.size()) {
            for(int j = i; j < K; j++) {
                ans += dp[j] * ps[i];
                ans %= MOD;
            }
        }
        cout << ans << endl;

    }
    return 0;
}

/* vim:set foldmethod=marker: */
0