結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
コンテスト
ユーザー ichyo
提出日時 2015-05-23 00:13:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 7,302 bytes
コンパイル時間 1,831 ms
コンパイル使用メモリ 178,388 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-06 05:44:26
合計ジャッジ時間 4,025 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 3
権限があれば一括ダウンロードができます

ソースコード

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);
}
//}}}
// ModInt (ref. anta) {{{
template<int MOD>
struct ModInt{
    static const int Mod = MOD;
    unsigned val;
    ModInt():val(0){}
    ModInt(unsigned x):val(x%MOD){}
    ModInt(signed x) {
        int y = x % MOD;
        if(y < 0) y += MOD;
        val = y;
    }
    ModInt(signed long long x) {
        int y = x % MOD;
        if(y < 0) y += MOD;
        val = y;
    }

    ModInt &operator+=(ModInt rhs) {
        val += rhs.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }
    ModInt &operator-=(ModInt rhs) {
        val += MOD - rhs.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }
    ModInt &operator*=(ModInt rhs) {
        val = (unsigned long long)val * rhs.val % MOD;
        return *this;
    }
    ModInt &operator/=(ModInt rhs) {
        return *this *= rhs.inv();
    }

    ModInt inv() const {
        signed a = val, b = MOD, u = 1, v = 0;
        while(b) {
            signed t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        if(u < 0) u += MOD;
        ModInt res;
        res.val = u;
        return res;
    }

    ModInt operator+(ModInt rhs) const {
        return ModInt(*this) += rhs;
    }
    ModInt operator-(ModInt rhs) const {
        return ModInt(*this) -= rhs;
    }
    ModInt operator*(ModInt rhs) const {
        return ModInt(*this) *= rhs;
    }
    ModInt operator/(ModInt rhs) const {
        return ModInt(*this) /= rhs;
    }

    // compare
    bool operator==(ModInt rhs) const {
        return val == rhs.val;
    }
    bool operator!=(ModInt rhs) const {
        return val != rhs.val;
    }
    bool operator< (ModInt rhs) const {
        return val <  rhs.val;
    }
    bool operator<=(ModInt rhs) const {
        return val <= rhs.val;
    }
    bool operator> (ModInt rhs) const {
        return val >  rhs.val;
    }
    bool operator>=(ModInt rhs) const {
        return val >= rhs.val;
    }
};
template<int MOD>
ostream& operator << (ostream& os, const ModInt<MOD> m) {
    return os << m.val;
}
template<int MOD, typename T>
ModInt<MOD> pow(ModInt<MOD> a, T b) {
    if(b == 0) {
        return 1;
    } else {
        auto w = pow(a*a, b/2);
        if(b&1) w *= a;
        return w;
    }
}
// }}}
typedef ModInt<1000000007> mint;
// {{{ http://nitcoder000.hatenablog.com/entry/kitamasa
#define MAX_LOGN 64
#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define all(b) (b).begin(),(b).end()
template <class T>
struct Mr{
	vector<T> first;
	vector<T> C;
	vector<vector<T>> bin;
	T zero,one;
	int M;
	//n(1,,,2M)をn(1,,,M)に修正、O(M^2)
	void form(vector<T> &n){
		rev(i, M + 1, 2 * M + 1){
			reE(j, 1, M)n[i - j] = (n[i - j] + (C[M - j] * n[i]));
			n[i] = zero;
		}
	}
	//lとrを足し合わせる、O(M^2)
	void add(vector<T> &l, vector<T> &r, vector<T> &ans){
		reE(i, 1, 2 * M)ans[i] = zero;
		reE(i, 1, M)reE(j, 1, M)ans[i + j] = (ans[i + j] + (l[i] * r[j]));
		form(ans);
	}
	//初期化、O(M*MAX_LOGN)
	Mr(const vector<T>& f,const vector<T>& c,int m,T e1,T e0){
		M = m;
		first.reserve(M + 1);C.reserve(M);
		zero = e0, one = e1;
		first.push_back(zero); 
		rT(i, M){ first.push_back(f[i]); C.push_back(c[i]); }
		bin.resize(MAX_LOGN);
		rT(i, MAX_LOGN)bin[i].resize(2*M+1);
		rE(i, 2*M)bin[0][i] = zero; bin[0][1] = one;
		reT(i,1, MAX_LOGN){
			add(bin[i - 1], bin[i - 1], bin[i]);
		}
	}
	//N項目の計算、戻り値がTの形であることに注意、O(M^2*logN)
	pair<T, vector<T>> calc(LL n){
		n--;
		vector<T> tmp,result = bin[0];
		for (int b = 0; n; b++,n>>=1)
			if (1 & n){ tmp = result; add(tmp, bin[b], result); }
		T ans = zero;
		reE(i, 1, M)ans = ans + (result[i] * first[i]);
		return make_pair(ans, result);
	}
    pair<T, vector<T>> next(vector<T> result) {
        vector<T> tmp = result;
        add(tmp, bin[0], result);
		T ans = zero;
		reE(i, 1, M)ans = ans + (result[i] * first[i]);
		return make_pair(ans, result);
    }
};
// }}}
//

vector<mint> generate(int P, vector<int> a) {
    assert(a.size() == 6);
    int K = P * a.back() + 1;
    const int MAX_S = 651;
    mint dp[MAX_S][6] = {};
    dp[0][0] = 1;
    REP(_, P) {
        mint ndp[MAX_S][6] = {};
        REP(s, MAX_S) REP(i, 6) {
            for(int j = i; j < 6; j++) {
                int ns = s + a[j];
                int ni = j;
                if(ns < MAX_S) {
                    ndp[ns][ni] += dp[s][i];
                }
            }
        }
        REP(i, MAX_S) REP(j, 6) dp[i][j] = ndp[i][j];
    }
    vector<mint> res(K);
    REP(i, K) REP(j, 6) res[i] += dp[i][j];
    return res;
}

int main(){
    iostream_init();
    LL n;
    while(cin >> n) {
        int P, C;
        cin >> P >> C;
        vector<mint> dp1 = generate(P, {2, 3, 5, 7, 11, 13});
        vector<mint> dp2 = generate(C, {4, 6, 8, 9, 10, 12});
        vector<mint> dp(dp1.size() + dp2.size() - 2);
        REP(i, dp1.size()) REP(j, dp2.size())if(i+j > 1) dp[i+j-1] += dp1[i] * dp2[j];
        int K = dp.size();

        vector<mint> first(K);
        first[K-1] = 1;

        vector<mint> cof(K);
        for(int i = 0; i < K; i++) cof[i] = dp[K-1-i];

        Mr<mint> kitamasa(first, cof, K, mint(1), mint(0));

        vector<mint> ps(K);
        vector<mint> result;
        bool isfirst = true;
        for(int i = n-1-(K-1), j=K-1; i <= n-1; i++, j--) {
            assert(n-1-j == i);
            assert(j < ps.size() && j >= 0);
            if(i > 0) {
                if(isfirst) {
                    isfirst = false;
                    auto p = kitamasa.calc(i + K);
                    ps[j] = p.first;
                    result = p.second;
                } else {
                    auto p = kitamasa.next(result);
                    ps[j] = p.first;
                    result = p.second;
                }
            } else {
                ps[j] = (i == 0 ? 1 : 0);
            }
        }
        
        mint ans = 0;
        REP(i, ps.size()) {
            for(int j = i; j < K; j++) {
                ans += dp[j] * ps[i];
            }
        }
        cout << ans << endl;

    }
    return 0;
}

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