結果
問題 | No.2120 場合の数の下8桁 |
ユーザー |
![]() |
提出日時 | 2022-11-04 21:41:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 17,208 bytes |
コンパイル時間 | 2,366 ms |
コンパイル使用メモリ | 194,896 KB |
実行使用メモリ | 10,984 KB |
最終ジャッジ日時 | 2024-07-18 19:24:11 |
合計ジャッジ時間 | 3,665 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <deque>#include <forward_list>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iostream>#include <limits>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using lint = long long;using pint = pair<int, int>;using plint = pair<lint, lint>;struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;#define ALL(x) (x).begin(), (x).end()#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)template <typename T, typename V>void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os <<']'; return os; }template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v<< ','; os << ']'; return os; }#if __cplusplus >= 201703Ltemplate <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);},tpl); return is; }template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) {((os << args << ','), ...);}, tpl); return os << ')'; }#endiftemplate <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os<< v << ','; os << '}'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os <<']'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}';return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os <<'}'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v <<','; os << '}'; return os; }template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for(auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }#ifdef HITONANODE_LOCALconst string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET<< std::endl#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " <<__FILE__ << COLOR_RESET << std::endl : std::cerr)#else#define dbg(x) ((void)0)#define dbgif(cond, x) ((void)0)#endif// Linear sieve algorithm for fast prime factorization// Complexity: O(N) time, O(N) space:// - MAXN = 10^7: ~44 MB, 80~100 ms (Codeforces / AtCoder GCC, C++17)// - MAXN = 10^8: ~435 MB, 810~980 ms (Codeforces / AtCoder GCC, C++17)// Reference:// [1] D. Gries, J. Misra, "A Linear Sieve Algorithm for Finding Prime Numbers,"// Communications of the ACM, 21(12), 999-1003, 1978.// - https://cp-algorithms.com/algebra/prime-sieve-linear.html// - https://37zigen.com/linear-sieve/struct Sieve {std::vector<int> min_factor;std::vector<int> primes;Sieve(int MAXN) : min_factor(MAXN + 1) {for (int d = 2; d <= MAXN; d++) {if (!min_factor[d]) {min_factor[d] = d;primes.emplace_back(d);}for (const auto &p : primes) {if (p > min_factor[d] or d * p > MAXN) break;min_factor[d * p] = p;}}}// Prime factorization for 1 <= x <= MAXN^2// Complexity: O(log x) (x <= MAXN)// O(MAXN / log MAXN) (MAXN < x <= MAXN^2)template <class T> std::map<T, int> factorize(T x) const {std::map<T, int> ret;assert(x > 0 andx <= ((long long)min_factor.size() - 1) * ((long long)min_factor.size() - 1));for (const auto &p : primes) {if (x < T(min_factor.size())) break;while (!(x % p)) x /= p, ret[p]++;}if (x >= T(min_factor.size())) ret[x]++, x = 1;while (x > 1) ret[min_factor[x]]++, x /= min_factor[x];return ret;}// Enumerate divisors of 1 <= x <= MAXN^2// Be careful of highly composite numbers https://oeis.org/A002182/list// https://gist.github.com/dario2994/fb4713f252ca86c1254d#file-list-txt (n, (# of div. of n)):// 45360->100, 735134400(<1e9)->1344, 963761198400(<1e12)->6720template <class T> std::vector<T> divisors(T x) const {std::vector<T> ret{1};for (const auto p : factorize(x)) {int n = ret.size();for (int i = 0; i < n; i++) {for (T a = 1, d = 1; d <= p.second; d++) {a *= p.first;ret.push_back(ret[i] * a);}}}return ret; // NOT sorted}// Euler phi functions of divisors of given x// Verified: ABC212 G https://atcoder.jp/contests/abc212/tasks/abc212_g// Complexity: O(sqrt(x) + d(x))template <class T> std::map<T, T> euler_of_divisors(T x) const {assert(x >= 1);std::map<T, T> ret;ret[1] = 1;std::vector<T> divs{1};for (auto p : factorize(x)) {int n = ret.size();for (int i = 0; i < n; i++) {ret[divs[i] * p.first] = ret[divs[i]] * (p.first - 1);divs.push_back(divs[i] * p.first);for (T a = divs[i] * p.first, d = 1; d < p.second; a *= p.first, d++) {ret[a * p.first] = ret[a] * p.first;divs.push_back(a * p.first);}}}return ret;}// Moebius function Table, (-1)^{# of different prime factors} for square-free x// return: [0=>0, 1=>1, 2=>-1, 3=>-1, 4=>0, 5=>-1, 6=>1, 7=>-1, 8=>0, ...] https://oeis.org/A008683std::vector<int> GenerateMoebiusFunctionTable() const {std::vector<int> ret(min_factor.size());for (unsigned i = 1; i < min_factor.size(); i++) {if (i == 1) {ret[i] = 1;} else if ((i / min_factor[i]) % min_factor[i] == 0) {ret[i] = 0;} else {ret[i] = -ret[i / min_factor[i]];}}return ret;}// Calculate [0^K, 1^K, ..., nmax^K] in O(nmax)// Note: **0^0 == 1**template <class MODINT> std::vector<MODINT> enumerate_kth_pows(long long K, int nmax) const {assert(nmax < int(min_factor.size()));assert(K >= 0);if (K == 0) return std::vector<MODINT>(nmax + 1, 1);std::vector<MODINT> ret(nmax + 1);ret[0] = 0, ret[1] = 1;for (int n = 2; n <= nmax; n++) {if (min_factor[n] == n) {ret[n] = MODINT(n).pow(K);} else {ret[n] = ret[n / min_factor[n]] * ret[min_factor[n]];}}return ret;}};Sieve sieve((1 << 20));// Solve ax+by=gcd(a, b)template <class Int> Int extgcd(Int a, Int b, Int &x, Int &y) {Int d = a;if (b != 0) {d = extgcd(b, a % b, y, x), y -= (a / b) * x;} else {x = 1, y = 0;}return d;}// Calculate a^(-1) (MOD m) s if gcd(a, m) == 1// Calculate x s.t. ax == gcd(a, m) MOD mtemplate <class Int> Int mod_inverse(Int a, Int m) {Int x, y;extgcd<Int>(a, m, x, y);x %= m;return x + (x < 0) * m;}// Require: 1 <= b// return: (g, x) s.t. g = gcd(a, b), xa = g MOD b, 0 <= x < b/gtemplate <class Int> /* constexpr */ std::pair<Int, Int> inv_gcd(Int a, Int b) {a %= b;if (a < 0) a += b;if (a == 0) return {b, 0};Int s = b, t = a, m0 = 0, m1 = 1;while (t) {Int u = s / t;s -= t * u, m0 -= m1 * u;auto tmp = s;s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;}if (m0 < 0) m0 += b / s;return {s, m0};}template <class Int>/* constexpr */ std::pair<Int, Int> crt(const std::vector<Int> &r, const std::vector<Int> &m) {assert(r.size() == m.size());int n = int(r.size());// Contracts: 0 <= r0 < m0Int r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert(1 <= m[i]);Int r1 = r[i] % m[i], m1 = m[i];if (r1 < 0) r1 += m1;if (m0 < m1) {std::swap(r0, r1);std::swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) return {0, 0};continue;}Int g, im;std::tie(g, im) = inv_gcd<Int>(m0, m1);Int u1 = m1 / g;if ((r1 - r0) % g) return {0, 0};Int x = (r1 - r0) / g % u1 * im % u1;r0 += x * m0;m0 *= u1;if (r0 < 0) r0 += m0;}return {r0, m0};}// 蟻本 P.262// 中国剰余定理を利用して,色々な素数で割った余りから元の値を復元// 連立線形合同式 A * x = B mod M の解// Requirement: M[i] > 0// Output: x = first MOD second (if solution exists), (0, 0) (otherwise)template <class Int>std::pair<Int, Int>linear_congruence(const std::vector<Int> &A, const std::vector<Int> &B, const std::vector<Int> &M) {Int r = 0, m = 1;assert(A.size() == M.size());assert(B.size() == M.size());for (int i = 0; i < (int)A.size(); i++) {assert(M[i] > 0);const Int ai = A[i] % M[i];Int a = ai * m, b = B[i] - ai * r, d = std::__gcd(M[i], a);if (b % d != 0) {return std::make_pair(0, 0); // 解なし}Int t = b / d * mod_inverse<Int>(a / d, M[i] / d) % (M[i] / d);r += m * t;m *= M[i] / d;}return std::make_pair((r < 0 ? r + m : r), m);}template <class Int = int, class Long = long long>Int pow_mod(Int x, long long n, Int md) {static_assert(sizeof(Int) * 2 <= sizeof(Long), "Watch out for overflow");if (md == 1) return 0;Int ans = 1;while (n > 0) {if (n & 1) ans = (Long)ans * x % md;x = (Long)x * x % md;n >>= 1;}return ans;}// nCr mod m = p^q (p: prime, q >= 1)// Can be used for n, r <= 1e18, m <= 1e7// Complexity: O(m) (construction), O(log(n)) (per query)// https://ferin-tech.hatenablog.com/entry/2018/01/17/010829struct combination_prime_pow {int p, q, m;std::vector<int> fac, invfac, ppow;long long _ej(long long n) const {long long ret = 0;while (n) ret += n, n /= p;return ret;}combination_prime_pow(int p_, int q_) : p(p_), q(q_), m(1), ppow{1} {for (int t = 0; t < q; ++t) m *= p, ppow.push_back(m);fac.assign(m, 1);invfac.assign(m, 1);for (int i = 1; i < m; ++i) fac[i] = (long long)fac[i - 1] * (i % p ? i : 1) % m;invfac[m - 1] = fac[m - 1]; // Same as Wilson's theoremassert(1LL * fac.back() * invfac.back() % m == 1);for (int i = m - 1; i; --i) invfac[i - 1] = (long long)invfac[i] * (i % p ? i : 1) % m;}int nCr(long long n, long long r) const {if (r < 0 or n < r) return 0;if (p == 2 and q == 1) return !((~n) & r); // Lucaslong long k = n - r;long long e0 = _ej(n / p) - _ej(r / p) - _ej(k / p);if (e0 >= q) return 0;long long ret = ppow[e0];if (q == 1) { // Lucaswhile (n) {ret = __int128(ret) * fac[n % p] * invfac[r % p] * invfac[k % p] % p;n /= p, r /= p, k /= p;}return (int)ret;} else {if ((p > 2 or q < 3) and (_ej(n / m) - _ej(r / m) - _ej(k / m)) & 1) ret = m - ret;while (n) {ret = __int128(ret) * fac[n % m] * invfac[r % m] * invfac[k % m] % m;n /= p, r /= p, k /= p;}return (int)ret;}}};// nCr mod m// Complexity: O(m) space worst (construction), O(log(n) log(m)) (per query)// Input: pairs of (prime, degree), such as vector<pair<int, int>> and map<int, int>// https://judge.yosupo.jp/problem/binomial_coefficientstruct combination {std::vector<combination_prime_pow> cpps;std::vector<int> ms;template <class Map> combination(const Map &p2deg) {for (auto f : p2deg) {cpps.push_back(combination_prime_pow(f.first, f.second));ms.push_back(cpps.back().m);}}int operator()(long long n, long long r) const {if (r < 0 or n < r) return 0;std::vector<int> rs;for (const auto &cpp : cpps) rs.push_back(cpp.nCr(n, r));return crt(rs, ms).first;}};int main() {int N, M;cin >> N >> M;combination ncr(sieve.factorize(100000000));string ret = to_string(ncr(N, M));while (ret.size() < 8) ret = "0" + ret;cout << ret << endl;}