結果
問題 | No.502 階乗を計算するだけ |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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());}