結果

問題 No.502 階乗を計算するだけ
ユーザー nok0nok0
提出日時 2021-03-04 22:54:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 733 ms / 1,000 ms
コード長 2,823 bytes
コンパイル時間 4,132 ms
コンパイル使用メモリ 164,428 KB
実行使用メモリ 8,160 KB
最終ジャッジ日時 2024-10-05 12:27:32
合計ジャッジ時間 35,470 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 719 ms
8,028 KB
testcase_01 AC 706 ms
8,032 KB
testcase_02 AC 721 ms
8,032 KB
testcase_03 AC 718 ms
8,032 KB
testcase_04 AC 728 ms
8,024 KB
testcase_05 AC 718 ms
8,156 KB
testcase_06 AC 718 ms
8,028 KB
testcase_07 AC 728 ms
8,032 KB
testcase_08 AC 715 ms
8,024 KB
testcase_09 AC 718 ms
8,028 KB
testcase_10 AC 712 ms
8,032 KB
testcase_11 AC 719 ms
8,028 KB
testcase_12 AC 713 ms
8,032 KB
testcase_13 AC 720 ms
8,028 KB
testcase_14 AC 718 ms
8,028 KB
testcase_15 AC 718 ms
8,024 KB
testcase_16 AC 713 ms
8,152 KB
testcase_17 AC 714 ms
8,156 KB
testcase_18 AC 714 ms
8,028 KB
testcase_19 AC 733 ms
8,032 KB
testcase_20 AC 714 ms
8,028 KB
testcase_21 AC 712 ms
8,032 KB
testcase_22 AC 715 ms
8,156 KB
testcase_23 AC 711 ms
8,152 KB
testcase_24 AC 709 ms
8,028 KB
testcase_25 AC 709 ms
8,028 KB
testcase_26 AC 708 ms
8,032 KB
testcase_27 AC 724 ms
8,024 KB
testcase_28 AC 731 ms
8,028 KB
testcase_29 AC 718 ms
7,896 KB
testcase_30 AC 709 ms
8,152 KB
testcase_31 AC 711 ms
8,160 KB
testcase_32 AC 710 ms
8,028 KB
testcase_33 AC 716 ms
8,028 KB
testcase_34 AC 704 ms
8,024 KB
testcase_35 AC 720 ms
8,032 KB
testcase_36 AC 705 ms
8,156 KB
testcase_37 AC 709 ms
8,156 KB
testcase_38 AC 710 ms
8,024 KB
testcase_39 AC 703 ms
8,028 KB
testcase_40 AC 721 ms
8,156 KB
testcase_41 AC 708 ms
8,156 KB
testcase_42 AC 2 ms
6,816 KB
testcase_43 AC 1 ms
6,820 KB
testcase_44 AC 2 ms
6,820 KB
testcase_45 AC 1 ms
6,820 KB
testcase_46 AC 2 ms
6,820 KB
testcase_47 AC 1 ms
6,820 KB
testcase_48 AC 2 ms
6,816 KB
testcase_49 AC 2 ms
6,816 KB
testcase_50 AC 1 ms
6,820 KB
testcase_51 AC 1 ms
6,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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());
}
0