結果
問題 | No.2120 場合の数の下8桁 |
ユーザー |
![]() |
提出日時 | 2022-11-04 23:36:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,482 bytes |
コンパイル時間 | 832 ms |
コンパイル使用メモリ | 104,888 KB |
実行使用メモリ | 81,548 KB |
最終ジャッジ日時 | 2024-07-18 21:23:59 |
合計ジャッジ時間 | 4,203 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 3 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#include <queue>#include <set>#include <random>#include <iomanip>using namespace std;typedef long long ll;#define rep(i, n) for(int i = 0; i < (n); i++)template<class T>using vi = vector<T>;template<class T>using vii = vector<vi<T>>;template<class T>using viii = vector<vii<T>>;void chmax(ll & x, ll y) { x = max(x, y); }void pf(int n, vi<int>& prime, vi<int>& cnt, bool plus = true) {if (n == 1) return;if (plus) cnt[prime[n]]++;else cnt[prime[n]]--;pf(n / prime[n], prime, cnt, plus);return;}ll modpow(ll x, ll n, ll mod) {if (n == 0) return 1LL;ll res = modpow(x, n / 2, mod);res *= res;res %= mod;if (n % 2) res *= x;res %= mod;return res;}int main(){int n, m;cin >> n >> m;vi<int> prime(n + 1);prime[1] = 1;for (int i = 2; i <= n; i++) {if (prime[i]) continue;prime[i] = i;for (ll j = (ll)i * i; j <= n; j += i) {if (prime[j]) continue;prime[j] = i;}}prime[1] = 1;vi<int> cnt(n + 1);m = min(n - m, m);rep(i, m) {pf(n - i, prime, cnt);pf(m - i, prime, cnt, false);}ll ans = 1;const ll mod = 1e8;for (int i = 2; i <= n; i++) {if (cnt[i] == 0) continue;ans *= modpow(i, cnt[i], mod);ans %= mod;}printf("%08d\n", ans);return 0;}