結果

問題 No.502 階乗を計算するだけ
ユーザー nok0
提出日時 2021-03-04 22:54:01
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,823 bytes
コンパイル時間 14,127 ms
コンパイル使用メモリ 198,308 KB
最終ジャッジ日時 2025-01-19 10:13:52
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

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