結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー Kmcode1Kmcode1
提出日時 2015-05-22 23:38:04
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,588 bytes
コンパイル時間 938 ms
コンパイル使用メモリ 107,572 KB
実行使用メモリ 21,240 KB
最終ジャッジ日時 2023-09-20 10:06:37
合計ジャッジ時間 1,368 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define R 36041
#define _R 85227895

#define N 131072
#define INF 9212376920367300606LL

int m, rm, _m, _rm, p;
long long n;

int modPow(int a, long long n) {
	int res(1);
	for (; n; n >>= 1, a = 1LL * a * a % MOD) if (n & 1) res = 1LL * res * a % MOD;
	return res;
}

int mod[N], rmod[N];
void build() {
	int i;
	for (m = 1; 4 * p >= m; m <<= 1);
	rm = modPow(m, MOD - 2);
	for (mod[0] = i = 1; i < N; i++) mod[i] = 1LL * mod[i - 1] * R % MOD;
	for (rmod[0] = i = 1; i < N; i++) rmod[i] = 1LL * rmod[i - 1] * _R % MOD;
}

inline int EXP(int d, int p, int m) {
	if (d > 0) return mod[N / m * p];
	return rmod[N / m * p];
}

void FFT(int *in, int *out, int step, int size, int d) {
	if (size == 1) {
		out[0] = in[0];
		return;
	}
	size >>= 1;
	FFT(in, out, step * 2, size, d);
	FFT(in + step, out + size, step * 2, size, d);
	int i, even, odd;
	for (i = 0; i < size; i++) {
		even = out[i], odd = out[i + size];
		out[i] = (1LL * EXP(d, i, size << 1) * odd + even) % MOD;
		out[i + size] = (1LL * EXP(d, i + size, size << 1) * odd + even) % MOD;
	}
}

int _a[N << 1], _b[N << 1], _ab[N << 1], _c[N << 1];

void multi(int *a, int *_b, int p, int *c, int st, int en) {
	for (_m = 1; 2 * p >= _m; _m <<= 1);
	_rm = modPow(_m, MOD - 2);
	for (int i = p; i < _m; i++) a[i] = 0;
	FFT(a, _a, 1, _m, 1);
	for (int i = 0; i < _m; i++) _ab[i] = 1LL * _a[i] * _b[i] % MOD;
	FFT(_ab, _c, 1, _m, -1);
	for (int i = 0; i < en - st; i++) c[i] = 1LL * _c[i + st] * _rm % MOD;
	for (int i = en - st; i < _m; i++) c[i] = 0;
}

void sqr(int *a, int p, int *b) {
	FFT(a, _a, 1, m, 1);
	for (int i = 0; i < m; i++) _ab[i] = 1LL * _a[i] * _a[i] % MOD;
	FFT(_ab, _b, 1, m, -1);
	for (int i = 0; i < p; i++) b[i] = 1LL * _b[i] * rm % MOD;
}

vector<long long> P;
int a[N << 1], c[N << 1], _I[N << 1], I[N << 1], _Q[N << 1], Q[N << 1], C[N << 1], _S[N << 1], _C[N << 1], S[N << 1], _B[N << 1], A[N << 1], B[N << 1], D[N << 1];

long long int aa[6] = { 2, 3, 5, 7, 11, 13 };
long long int b[6] = { 4, 6, 8, 9, 10, 12 };
vector<int> cc;
class make{
public:
	vector<int> v;
#define MAX 102
	bool dp[MAX][10][10];  //何回目,sump sums
	bool use[MAX];
#define MOD 1000000007
	long long int a[MAX];
	long long int n;
	make(){
		cc.clear();
		scanf("%lld", &n);
		int p, c;
		cin >> p >> c;

		dp[0][0][0] = true;
		for (int i = 0; i < MAX; i++){
			for (int j = 0; j <= p; j++){
				for (int k = 0; k <= c; k++){
					if (dp[i][j][k]){
						use[i] = true;
						for (int kk = 0; kk < 6; kk++){
							if (j < p){
								dp[i + aa[kk]][j + 1][k] = true;
								use[i + aa[kk]] = true;
							}
							if (k  < c){
								dp[i + b[kk]][j][k + 1] = true;
								use[i + b[kk]] = true;
							}
						}
					}
				}
			}
		}
		cc.clear();
		for (int i = 1; i < MAX; i++){
			if (use[i]){
				cc.push_back(i);
			}
		}
		a[0] = 1LL;
		for (int i = 0; i < MAX; i++){
			for (int j = 0; j < cc.size(); j++){
				if (i + cc[j] < MAX){
					a[i + cc[j]] += a[i];
					a[i + cc[j]] %= MOD;
				}
			}
		}
	}
};
make mk;
int ccc[MAX];
int main() {
	int i, j, ans, cur;
	long long q;
	p = cc.back();
	n = mk.n;
	n++;
//	scanf("%d%lld", &p, &n);
	for (int i = 0; i < p; i++){
		a[i] = mk.a[i];
	}
	for (int i = 0; i < cc.size(); i++){
		ccc[p-cc[i]]=true;
	}
	for (int i = 0; i < p; i++){
		c[i] = ccc[i];
	}
//	for (i = 0; i < p; i++) scanf("%d", &a[i]);
	//for (i = 0; i < p; i++) scanf("%d", &c[i]);
	if (n <= p) {
		printf("%d\n", a[n - 1]);
		return 0;
	}
	if (p == 1) {
		ans = 1LL * a[0] * modPow(c[0], n - 1) % MOD;
		printf("%d\n", ans);
		return 0;
	}
	build();
	n--;
	for (j = 1; j <= p; j++) _I[j] = c[j - 1];
	FFT(_I, I, 1, m, 1);

	for (C[0] = 1, j = 1; j < p; j++) C[j] = (MOD - c[j - 1]) % MOD;

	for (q = 2 * p - 1; q; q >>= 1) P.push_back(q);

	for (i = P.size() - 1; i >= 0; i--) {
		q = P[i];
		if (q == 1) {
			S[0] = 1;
			for (j = 1; j <= p; j++) Q[j] = c[j - 1];
			continue;
		}

		Q[0] = (Q[0] + 1) % MOD;
		for (j = 2 * p - 1; j < m; j++) S[j] = Q[j] = 0;
		FFT(Q, _Q, 1, m, 1);
		FFT(S, _S, 1, m, 1);
		for (j = 0; j < m; j++) _S[j] = 1LL * _S[j] * _Q[j] % MOD;
		FFT(_S, S, 1, m, -1);
		for (j = 0; j < 2 * p - 1; j++) S[j] = 1LL * S[j] * rm % MOD;
		Q[0] = (Q[0] + MOD - 1) % MOD;

		for (j = 0; j < m; j++) {
			_Q[j] = 1LL * (_Q[j] - 1) * (_Q[j] - 1) % MOD;
			if (_Q[j] < 0) _Q[j] += MOD;
		}

		FFT(_Q, Q, 1, m, -1);
		for (j = 0; j < 2 * p - 1; j++) Q[j] = 1LL * Q[j] * rm % MOD;

		if (q & 1) {
			for (j = 0; j < 2 * p - 1; j++) S[j] = (S[j] + Q[j]) % MOD;
			for (j = 2 * p - 1; j < m; j++) Q[j] = 0;
			FFT(Q, _Q, 1, m, 1);
			for (j = 0; j < m; j++) _Q[j] = 1LL * _Q[j] * I[j] % MOD;
			FFT(_Q, Q, 1, m, -1);
			for (j = 0; j < 2 * p - 1; j++) Q[j] = 1LL * Q[j] * rm % MOD;

		}
	}
	for (i = 2 * p - 1; i < m; i++) S[i] = 0;
	int _m = m >> 1, _rm = modPow(_m, MOD - 2);
	FFT(S, _S, 1, m, 1);
	FFT(C, _C, 1, _m, 1);
	P.clear();
	for (q = n; q; q >>= 1) P.push_back(q);
	A[p - 1] = 1;
	for (i = P.size() - 1; i >= 0; i--) {
		q = P[i];
		if (q < 2 * p - 1) {
			for (j = 0; j < p; j++) A[j] = ((q + j >= p - 1) ? S[q + j - p + 1] : 0);
			continue;
		}
		multi(A, _C, p, B, 0, p);
		for (j = _m; j < m; j++) B[j] = 0;
		FFT(B, D, 1, _m, 1);
		for (j = 0; j < _m; j++) D[j] = 1LL * D[j] * D[j] % MOD;
		FFT(D, B, 1, _m, -1);
		for (j = 0; j < 2 * p - 1; j++) B[j] = 1LL * B[j] * _rm % MOD;
		FFT(B, D, 1, m, 1);
		for (j = 0; j < m; j++) D[j] = 1LL * D[j] * _S[j] % MOD;
		FFT(D, A, 1, m, -1);
		for (j = 0; j < p; j++) A[j] = 1LL * A[j + p - 1] * rm % MOD;
		if (q & 1) {
			for (cur = 1LL * A[0] * c[p - 1] % MOD, j = 0; j < p - 1; j++) A[j] = A[j + 1];
			for (j = 0; j < p - 1; j++) cur = (1LL * A[j] * c[p - 2 - j] + cur) % MOD;
			A[p - 1] = cur;
		}
	}
	FFT(a, _a, 1, _m, 1);
	for (i = 0; i < _m; i++) _a[i] = 1LL * _a[i] * _C[i] % MOD;
	FFT(_a, D, 1, _m, -1);
	for (i = 0; i < p; i++) D[i] = 1LL * D[i] * _rm % MOD;
	for (i = p; i < _m; i++) A[i] = D[i] = 0;
	FFT(A, _a, 1, _m, 1);
	FFT(D, a, 1, _m, 1);
	for (i = 0; i < _m; i++) _a[i] = 1LL * _a[i] * a[i] % MOD;
	FFT(_a, B, 1, _m, -1);
	ans = 1LL * B[p - 1] * _rm % MOD;
	printf("%d\n", ans);
	return 0;
}
0