結果
問題 | No.2120 場合の数の下8桁 |
ユーザー | boatmuscles |
提出日時 | 2022-11-04 22:41:35 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,953 bytes |
コンパイル時間 | 1,779 ms |
コンパイル使用メモリ | 141,696 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-18 20:38:07 |
合計ジャッジ時間 | 3,456 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 RE * 6 WA * 4 |
ソースコード
#include<cstdio>#include<vector>#include<map>#include<atcoder/modint>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds;using namespace std;using namespace atcoder;using mint = modint;#define rep(i, n) for (int i = 0; i < (int)(n); ++i)#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)#define rep2(i, a, b) for (int i = (int)a; i < (int)(b); ++i)#define rrep2(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); --i)constexpr int MAX_N = 4000;int prime_divisor[MAX_N+1];//prime_divisor[i]はiを割り切る素数の1つvector<int> primes = {2};int main(){int M, N;scanf("%d\n%d", &M, &N);if(M < N){printf("00000000\n");return 0;}for (int i = 4; i <= MAX_N; i += 2){prime_divisor[i] = 2;}int _i = 3;for (int twoi; _i*_i <= MAX_N; _i += 2){if(!prime_divisor[_i]){primes.push_back(_i);twoi = _i<<1;for (int j = _i*_i; j <= MAX_N; j += twoi){prime_divisor[j] = _i;}}}for (; _i <= MAX_N; _i += 2) if(!prime_divisor[_i]) primes.push_back(_i);gp_hash_table<int, int> prime_factorization;//注目している数を素因数分解したときの<素因数, 割り切る回数>auto solve = [&](int x, bool add){int __x = x;for(auto &i : primes){if(__x < i) break;int cnt = 0, _x = __x;while((_x /= i)){cnt += _x;}prime_factorization[i] += add ? cnt : -cnt;while(!(x%i)) x /= i;}if(x != 1) prime_factorization[x] += add ? 1 : -1;};solve(M, true);solve(N, false);solve(M-N, false);mint::set_mod(100000000);mint answer{1};for(auto [num, pow] : prime_factorization) answer *= mint::raw(num).pow(pow);printf("%08u\n", answer.val());return 0;}