#625075 (C++17) No.502 階乗を計算するだけ

提出ソース

結果

問題	No.502 階乗を計算するだけ
ユーザー	nok0
提出日時	2021-03-04 22:54:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	825 ms / 1,000 ms
コード長	2,823 bytes
コンパイル時間	4,317 ms
コンパイル使用メモリ	162,096 KB
実行使用メモリ	8,672 KB
最終ジャッジ日時	2024-04-15 14:38:56
合計ジャッジ時間	40,691 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	810 ms 8,548 KB
testcase_01	AC	811 ms 8,544 KB
testcase_02	AC	814 ms 8,548 KB
testcase_03	AC	812 ms 8,544 KB
testcase_04	AC	807 ms 8,544 KB
testcase_05	AC	809 ms 8,544 KB
testcase_06	AC	815 ms 8,544 KB
testcase_07	AC	807 ms 8,548 KB
testcase_08	AC	806 ms 8,672 KB
testcase_09	AC	808 ms 8,544 KB
testcase_10	AC	808 ms 8,544 KB
testcase_11	AC	809 ms 8,544 KB
testcase_12	AC	811 ms 8,544 KB
testcase_13	AC	812 ms 8,412 KB
testcase_14	AC	811 ms 8,544 KB
testcase_15	AC	814 ms 8,548 KB
testcase_16	AC	810 ms 8,548 KB
testcase_17	AC	808 ms 8,540 KB
testcase_18	AC	810 ms 8,672 KB
testcase_19	AC	811 ms 8,540 KB
testcase_20	AC	809 ms 8,540 KB
testcase_21	AC	810 ms 8,416 KB
testcase_22	AC	806 ms 8,540 KB
testcase_23	AC	808 ms 8,544 KB
testcase_24	AC	808 ms 8,548 KB
testcase_25	AC	811 ms 8,544 KB
testcase_26	AC	811 ms 8,544 KB
testcase_27	AC	809 ms 8,540 KB
testcase_28	AC	808 ms 8,544 KB
testcase_29	AC	811 ms 8,544 KB
testcase_30	AC	816 ms 8,416 KB
testcase_31	AC	813 ms 8,544 KB
testcase_32	AC	814 ms 8,544 KB
testcase_33	AC	813 ms 8,544 KB
testcase_34	AC	810 ms 8,544 KB
testcase_35	AC	808 ms 8,548 KB
testcase_36	AC	818 ms 8,544 KB
testcase_37	AC	825 ms 8,544 KB
testcase_38	AC	816 ms 8,540 KB
testcase_39	AC	811 ms 8,544 KB
testcase_40	AC	806 ms 8,544 KB
testcase_41	AC	810 ms 8,544 KB
testcase_42	AC	3 ms 6,940 KB
testcase_43	AC	2 ms 6,944 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	2 ms 6,940 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	2 ms 6,944 KB
testcase_49	AC	2 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <atcoder/all>

using mint = atcoder::modint1000000007;

long long garner(std::vector<int> r, std::vector<int> m, const int mod) {
	assert(r.size() == m.size());
	m.emplace_back(mod);
	std::vector<long long> coeffs(m.size(), 1);
	std::vector<long long> constants(m.size(), 0);
	for(int k = 0; k < (int)r.size(); k++) {
		atcoder::modint::set_mod(m[k]);
		long long t = (atcoder::modint(r[k] - constants[k]) / coeffs[k]).val();
		for(int i = k + 1; i < (int)m.size(); i++) {
			(constants[i] += t * coeffs[i]) %= m[i];
			(coeffs[i] *= m[k]) %= m[i];
		}
	}
	return constants.back();
}

std::vector<mint> anymod_convolution(const std::vector<mint> &a, const std::vector<mint> &b) {
	const int m1 = 167772161;
	const int m2 = 469762049;
	const int m3 = 1224736769;
	std::vector<int> c, d;
	for(auto &v : a) c.emplace_back(v.val());
	for(auto &v : b) d.emplace_back(v.val());
	auto x = atcoder::convolution<m1>(c, d);
	auto y = atcoder::convolution<m2>(c, d);
	auto z = atcoder::convolution<m3>(c, d);
	std::vector<mint> ret(x.size());
	std::vector<int> r, m = {m1, m2, m3};
	for(int i = 0; i < (int)x.size(); i++) {
		r = {x[i], y[i], z[i]};
		ret[i] = garner(r, m, mint::mod());
	}
	return ret;
}

mint anymod_fast_mod_factorial(long long n) {
	if(n >= mint::mod()) return 0;
	const int d = 1 << 15;
	std::vector<mint> finv(d + 1);
	mint b = 1;
	for(int i = 2; i <= d; i++) b *= i;
	finv[d] = b.inv();
	for(int i = d; i; i--) finv[i - 1] = finv[i] * i;
	std::vector<mint> seq({1, d + 1});
	seq.reserve(d + 1);
	int sz = 1;
	while(sz < d) {
		std::vector<mint> aux(sz, 1), f(sz * 4), g(sz * 4);
		for(int i = 0; i <= sz; i++) {
			f[i] = finv[i] * finv[sz - i] * seq[i];
			if((sz + i & 1) and f[i] != 0) f[i] *= -1;
		}
		std::vector<mint> pf(f), as;
		as.emplace_back(sz + 1);
		as.emplace_back(mint(sz) / d);
		as.emplace_back(mint(sz) / d + sz + 1);
		for(int idx = 0; idx < 3; idx++) {
			for(int i = 0; i < sz * 4; i++) f[i] = pf[i];
			for(int i = 1; i < sz * 2 + 2; i++) g[i] = (as[idx] - (sz - i + 1)).inv();
			f = anymod_convolution(f, g);
			f.resize(sz * 4);
			mint prod = 1;
			for(int i = 0; i <= sz; i++) prod *= as[idx] - i;
			for(int i = 0; i <= sz; i++) {
				f[sz + i + 1] *= prod;
				prod *= as[idx] + i + 1;
				prod /= as[idx] - (sz - i);
			}
			if(idx == 0)
				for(int i = 0; i < sz; i++) aux[i] = f[sz + i + 1];
			if(idx == 1)
				for(int i = 0; i <= sz; i++) seq[i] *= f[sz + i + 1];
			if(idx == 2)
				for(int i = 0; i < sz; i++) aux[i] *= f[sz + i + 1];
		}
		for(auto x : aux) seq.emplace_back(x);
		sz <<= 1;
	}
	mint res = 1;
	int l = std::min((long long)d, (n + 1) / d);
	for(int i = 0; i < l; i++) res *= seq[i];
	for(int i = l * d + 1; i <= n; i++) res *= i;
	return res;
}

long long x;
int main() {
	scanf("%lld", &x);
	printf("%d\n", anymod_fast_mod_factorial(x).val());
}

yukicoder

結果

テストケース

ソースコード