結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
ユーザー pekempeypekempey
提出日時 2017-01-11 20:26:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,682 ms / 4,000 ms
コード長 5,633 bytes
コンパイル時間 2,268 ms
コンパイル使用メモリ 185,944 KB
実行使用メモリ 24,068 KB
最終ジャッジ日時 2024-06-01 06:13:13
合計ジャッジ時間 7,867 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,682 ms
23,772 KB
testcase_01 AC 1,677 ms
24,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
typedef __int128_t int128;

class Karatsuba128 {
private:
	int mod;

public:
	Karatsuba128(int mod) : mod(mod) {}

	std::vector<int> mul(std::vector<int> a, std::vector<int> b, int pmod = -1) {
		if (pmod == -1) pmod = a.size() + b.size() - 1;
		else {
			if (a.size() > pmod) a.resize(pmod);
			if (b.size() > pmod) b.resize(pmod);
		}
		int s = std::max<int>(a.size(), b.size());
		int t = 1;
		while (t < s) t *= 2;
		std::vector<int64_t> A(t), B(t), C(t * 4);
		std::vector<int128> res(t * 4);
		for (int i = 0; i < a.size(); i++) A[i] = a[i];
		for (int i = 0; i < b.size(); i++) B[i] = b[i];
		mul(A.data(), B.data(), C.data(), t, res.data());
		std::vector<int> c(pmod);
		for (int i = 0; i < std::min<int>(pmod, C.size()); i++) {
			c[i] = res[i] % mod;
			if (c[i] < 0) c[i] += mod;
		}
		return c;
	}

private:
	void mul(int64_t a[], int64_t b[], int64_t c[], int n, int128 res[]) {
		if (n <= 8) {
			memset(res, 0, sizeof(res[0]) * n * 2);
			for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
				res[i + j] += int128(a[i]) * b[j];
			}
			return;
		}
		int64_t *a0 = a, *a1 = a + n / 2;
		int64_t *b0 = b, *b1 = b + n / 2;
		int64_t *c0 = c, *c1 = c + n / 2;
		int128 *x0 = res, *x1 = res + n, *x2 = res + n * 2;
		for (int i = 0; i < n / 2; i++) {
			c0[i] = a0[i] + a1[i];
			c1[i] = b0[i] + b1[i];
		}
		mul(a0, b0, c + n * 2, n / 2, x0);
		mul(a1, b1, c + n * 2, n / 2, x1);
		mul(c0, c1, c + n * 2, n / 2, x2);
		for (int i = 0; i < n; i++) x2[i] -= x0[i] + x1[i];
		for (int i = 0; i < n; i++) res[i + n / 2] += x2[i];
	}
};

class AnyModPolynomial {
private:
	int mod;
	Karatsuba128 kara128;

	std::vector<int> t;

public:
	AnyModPolynomial(int mod) : mod(mod), kara128(mod) {}

	std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b) {
		return kara128.mul(a, b);
	}

	std::vector<int> add(const std::vector<int> &a, const std::vector<int> &b) {
		std::vector<int> res(std::max<int>(a.size(), b.size()));
		for (int i = 0; i < res.size(); i++) {
			res[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
		}
		return res;
	}

	std::vector<int> sub(const std::vector<int> &a, const std::vector<int> &b) {
		std::vector<int> res(std::max<int>(a.size(), b.size()));
		for (int i = 0; i < res.size(); i++) {
			res[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? (mod - b[i]) : 0);
		}
		return res;
	}

	std::vector<int> quot(std::vector<int> a, std::vector<int> b) {
		if (a.size() < b.size()) return{ 0 };
		while (b.back() == 0) b.pop_back();
		int s = a.size() - b.size() + 1;
		while (!is_pow2(a.size() - b.size() + 1)) a.push_back(0);
		int n = a.size() - b.size() + 1;
		if (t.empty()) t = inv(rev(b), n);
		std::vector<int> q = rev(mul(rev(a), t, n));
		q.resize(s);
		return q;
	}

	std::vector<int> rem(std::vector<int> a, std::vector<int> b) {
		while (b.back() == 0) b.pop_back();
		std::vector<int> r = sub(a, mul(quot(a, b), b, b.size() - 1));
		r.resize(b.size() - 1);
		return r;
	}

	std::vector<int> remmul(std::vector<int> a, std::vector<int> b, std::vector<int> c) {
		return rem(mul(a, b), c);
	}

	std::vector<int> remmulX(std::vector<int> a, std::vector<int> c) {
		a.resize(c.size() - 1);
		int tmp = a.back();
		for (int i = a.size() - 1; i >= 1; i--) {
			a[i] = a[i - 1];
		}
		a[0] = 0;
		for (int i = 0; i < a.size(); i++) {
			upd(a[i], mul(tmp, mod - c[i]));
		}
		return a;
	}

private:
	int pow(int64_t x, int64_t y, int mod) {
		int64_t res = 1;
		for (; y > 0; x = x * x % mod, y >>= 1) if (y & 1) res = res * x % mod;
		return res;
	}

	int inv(int x, int mod) {
		return pow(x, mod - 2, mod);
	}

	int is_pow2(int n) {
		return (n & (n - 1)) == 0;
	}

	int mul(int x, int y) {
		return int64_t(x) * y % mod;
	}

	int add(int x, int y) {
		return (x += y) >= mod ? x - mod : x;
	}

	void upd(int &x, int y) {
		x = add(x, y);
	}

	int pow(int x, int y) {
		int res = 1;
		for (; y > 0; x = mul(x, x), y >>= 1) if (y & 1) res = mul(res, x);
		return res;
	}

	int inv(int x) {
		return pow(x, mod - 2);
	}

	std::vector<int> mul(std::vector<int> a, std::vector<int> b, int n) {
		return kara128.mul(a, b, n);
	}

	std::vector<int> inv(std::vector<int> a, int n) {
		assert(is_pow2(n));
		std::vector<int> b(1);
		b[0] = inv(a[0]);
		for (int i = 0; (1 << i) < a.size(); i++) {
			b = sub(add(b, b), mul(mul(b, b), a, 1 << (i + 1)));
		}
		return b;
	}

	std::vector<int> rev(std::vector<int> a) {
		reverse(a.begin(), a.end());
		return a;
	}
};

const int mod = 1e9 + 7;

int64_t dp[2][301][4000], way[10000];

void calc(int64_t dp[301][4000], int64_t n, std::vector<int> dice) {
	dp[0][0] = 1;
	for (int k = 0; k < dice.size(); k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 3910; j++) {
				(dp[i + 1][j + dice[k]] += dp[i][j]) %= mod;
			}
		}
	}
}

int main() {
	using namespace std;
	int64_t N, P, C;
	cin >> N >> P >> C;
	calc(dp[0], P, { 2, 3, 5, 7, 11, 13 });
	calc(dp[1], C, { 4, 6, 8, 9, 10, 12 });
	for (int i = 0; i <= 3900; i++) {
		for (int j = 0; j <= 3900; j++) {
			(way[i + j] += dp[0][P][i] * dp[1][C][j]) %= mod;
		}
	}
	int64_t K = P * 13 + C * 12 + 1;
	vector<int> a(K + 1);
	for (int i = 0; i < K; i++) a[i] = mod - way[K - i];
	a[K] = 1;
	int64_t M = N + K - 1;
	AnyModPolynomial poly(mod);

	string s = bitset<62>(M).to_string();
	int i = 0;
	while (i < s.size() && s[i] == '0') i++;
	i++;
	vector<int> f = { 0, 1 };
	if (i == s.size()) {
		f[0] = 1;
		f[1] = 0;
	}
	for (; i < s.size(); i++) {
		f = poly.remmul(f, f, a);
		if (s[i] == '1') {
			f = poly.remmulX(f, a);
		}
	}
	int64_t ans = 0;
	for (int i = 0; i < K; i++) ans += int64_t(f[i]);
	cout << ans % mod << endl;
}
0