結果
問題 |
No.8120 Aoki's Present for Takahashi
|
ユーザー |
![]() |
提出日時 | 2025-04-01 22:28:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 488 ms / 2,000 ms |
コード長 | 2,063 bytes |
コンパイル時間 | 3,465 ms |
コンパイル使用メモリ | 285,888 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-04-01 23:15:48 |
合計ジャッジ時間 | 11,939 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <atcoder/math> #include <atcoder/modint> #include <bits/stdc++.h> using namespace std; typedef long long ll; // const int MOD = 1000000007; const int p0 = 443; const int p1 = 2253371; const int MOD = 998243353; // 443 * 2253371 using mint0 = atcoder::dynamic_modint<0>; using mint1 = atcoder::dynamic_modint<1>; struct comb0 { vector<pair<mint0, int>> cntp; comb0(int n) : cntp(n + 1) { cntp[0].first = 1; cntp[0].second = 0; for (int i = 1; i < n; i++) { cntp[i].second = cntp[i - 1].second; int tmp = i; while (tmp % mint0::mod() == 0) { cntp[i].second++; tmp /= mint0::mod(); } cntp[i].first = cntp[i - 1].first * tmp; } } mint0 c(ll n, ll r) { if (n < r || n < 0 || r < 0) return 0; int cnt = cntp[n].second - cntp[n - r].second - cntp[r].second; assert(cnt >= 0); if (cnt != 0) { return mint0(0); } else { return (cntp[n].first / cntp[n - r].first) / cntp[r].first; } } }; struct comb1 { vector<pair<mint1, int>> cntp; comb1(int n) : cntp(n + 1) { cntp[0].first = 1; cntp[0].second = 0; for (int i = 1; i < n; i++) { cntp[i].second = cntp[i - 1].second; int tmp = i; while (tmp % mint1::mod() == 0) { cntp[i].second++; tmp /= mint1::mod(); } cntp[i].first = cntp[i - 1].first * tmp; } } mint1 c(ll n, ll r) { if (n < r || n < 0 || r < 0) return 0; int cnt = cntp[n].second - cntp[n - r].second - cntp[r].second; assert(cnt >= 0); if (cnt != 0) { return mint1(0); } else { return (cntp[n].first / cntp[n - r].first) / cntp[r].first; } } }; int main() { mint0::set_mod(p0); mint1::set_mod(p1); int tt, tau; cin >> tt >> tau; comb0 c0(2e5 + 10); comb1 c1(2e5 + 10); for (int t = 1; t <= tau; t++) { int n, m; cin >> n >> m; if (t == tt) { cout << -1 << endl; } else { // cerr << mint0::mod() << endl; // cerr << mint1::mod() << endl; // cerr << c0.c(m, n).val() << endl; // cerr << c1.c(m, n).val() << endl; cout << atcoder::crt({c0.c(m, n).val(), c1.c(m, n).val()}, {p0, p1}).first << endl; } } return 0; }