結果
| 問題 | No.213 素数サイコロと合成数サイコロ (3-Easy) |
| ユーザー |
 ichyo
|
| 提出日時 | 2015-05-22 23:40:46 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 217 ms / 3,000 ms |
| コード長 | 6,156 bytes |
| コンパイル時間 | 1,799 ms |
| コンパイル使用メモリ | 174,124 KB |
| 実行使用メモリ | 6,940 KB |
| 最終ジャッジ日時 | 2024-07-06 05:37:57 |
| 合計ジャッジ時間 | 2,372 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 86 ms
6,812 KB |
| testcase_01 | AC | 217 ms
6,940 KB |
ソースコード
// 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)
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 ans;
}
};
// }}}
//
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);
}
}
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<mint> dp(K);
for(int x : res) dp[x-1] += 1;
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);
REP(i, ps.size()){
if(n-1-i > 0) {
ps[i] = kitamasa.calc(n-1-i + K);
} else {
ps[i] = (n-1-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: */