結果

問題 No.502 階乗を計算するだけ
ユーザー nok0nok0
提出日時 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());
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0