結果
問題 | No.2120 場合の数の下8桁 |
ユーザー |
![]() |
提出日時 | 2023-03-30 02:26:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,416 bytes |
コンパイル時間 | 4,297 ms |
コンパイル使用メモリ | 265,608 KB |
最終ジャッジ日時 | 2025-02-11 19:03:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 WA * 1 RE * 1 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")using namespace std;using namespace atcoder;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define repll(i, n) for (long long i = 0; i < (long long)(n); i++)#define rep2(i, n, m) for (int i = n; i < (int)(m); i++)#define repll2(i, n, m) for (long long i = n; i < (long long)(m); i++)#define all(v) v.begin(),v.end()using ll=long long;using ld=long double;using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;using vld=vector<ld>;using vvld=vector<vld>;int dx[8]={1,0,-1,0,1,1,-1,-1};int dy[8]={0,1,0,-1,1,-1,1,-1};const double PI = acos(-1);//const ll MOD=1e9+7;//const ll MOD=998244353;const ll INF=(1LL<<60);const int INF2=(1<<30);//using mint=modint1000000007;//using mint=modint998244353;// referece: https://37zigen.com/linear-sieve/class LinearSieve {public:LinearSieve(unsigned int n) : _n(n), min_prime_factor(std::vector<unsigned int>(n + 1)) {std::iota(min_prime_factor.begin(), min_prime_factor.end(), 0);prime_list.reserve(_n + 1);for (unsigned int d = 2; d <= _n; ++d) {if (min_prime_factor[d] == d) {prime_list.push_back(d);}unsigned int prime_max = std::min(min_prime_factor[d], _n / d);for (unsigned int prime : prime_list) {if (prime > prime_max) {break;}min_prime_factor[prime * d] = prime;}}}unsigned int prime_num() const {return prime_list.size();}const std::vector<unsigned int>& get_prime_list() const {return prime_list;}const std::vector<unsigned int>& get_min_prime_factor() const {return min_prime_factor;}private:const unsigned int _n;std::vector<unsigned int> min_prime_factor;std::vector<unsigned int> prime_list;};template <typename mint>class ArbitraryModBinomialCoefficients {public:ArbitraryModBinomialCoefficients(unsigned int N) :_N(N), _M(mint::mod()), _sieve(LinearSieve(N)), _binom(std::vector<mint>(N + 1)) {solve();}mint operator[](unsigned int k) const {return _binom[k];}const std::vector<mint>& get_coeffs() const {return _binom;}const LinearSieve& get_sieve() const {return _sieve;}private:const unsigned int _N, _M;const LinearSieve _sieve;std::vector<mint> _binom;void mod_invs(std::vector<mint>& invs) {auto &mpf = _sieve.get_min_prime_factor();if (_N >= 1) invs[1] = 1;for (unsigned int i = 2; i <= _N; ++i) {unsigned int pf = mpf[i];if (pf == i) {if (_M % pf) invs[i] = mint(i).inv();} else {invs[i] = invs[pf] * invs[i / pf];}}}void solve() {auto &primes = _sieve.get_prime_list();std::vector<unsigned int> d(_N + 1, 0);std::vector<unsigned int> p;for (unsigned int prime : primes) {if (_M % prime) continue;p.push_back(prime);unsigned int sz = p.size();for (unsigned int v = prime; v <= _N; v += prime) {d[v] = sz;}}const unsigned int L = p.size();p.insert(p.begin(), 0);std::vector<mint> invs(_N + 1);mod_invs(invs);std::vector<std::vector<mint>> powers(L + 1);for (unsigned int i = 1; i <= L; ++i) {unsigned int max_index = _N / (p[i] - 1);powers[i].resize(max_index + 1);mint pi = p[i];powers[i][0] = 1;for (unsigned int j = 0; j < max_index; ++j) {powers[i][j + 1] = powers[i][j] * pi;}}const unsigned int half = (_N + 1) / 2;mint S = 1;std::vector<unsigned int> T(L + 1, 0);_binom[0] = 1;for (unsigned int k = 1; k <= half; ++k) {unsigned int num = _N - k + 1, den = k;while (d[num]) ++T[d[num]], num /= p[d[num]];while (d[den]) --T[d[den]], den /= p[d[den]];S *= num * invs[den];_binom[k] = S;for (unsigned int i = 1; i <= L; ++i) {_binom[k] *= powers[i][T[i]];}}for (unsigned int k = half + 1; k <= _N; ++k) {_binom[k] = _binom[_N - k];}}};int main() {ios::sync_with_stdio(false);std::cin.tie(nullptr);using mint=atcoder::modint;mint::set_mod(100000000);int m,n;cin>>m>>n;ArbitraryModBinomialCoefficients<mint> AMBC(m);int v=AMBC[n].val();string ans=to_string(v);while(int(ans.size())<8)ans='0'+ans;cout<<ans<<endl;return 0;}