結果
問題 | No.8120 Aoki's Present for Takahashi |
ユーザー |
![]() |
提出日時 | 2025-04-01 23:08:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 1,381 bytes |
コンパイル時間 | 4,252 ms |
コンパイル使用メモリ | 252,548 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-04-01 23:18:10 |
合計ジャッジ時間 | 11,675 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = static_modint<998243353>; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL /* struct combi{ deque<mint> kaijou; deque<mint> kaijou_; combi(int n){ kaijou.push_back(1); for(int i=1;i<=n;i++){ kaijou.push_back(kaijou[i-1]*i); } mint b=kaijou[n].inv(); kaijou_.push_front(b); for(int i=1;i<=n;i++){ int k=n+1-i; kaijou_.push_front(kaijou_[0]*k); } } mint combination(int n,int r){ if(r>n)return 0; mint a = kaijou[n]*kaijou_[r]; a *= kaijou_[n-r]; return a; } mint junretsu(int a,int b){ mint x = kaijou_[a]*kaijou_[b]; x *= kaijou[a+b]; return x; } mint catalan(int n){ return combination(2*n,n)/(n+1); } }; combi C(500000); */ int get(int N){ int res = 0; while(N!=0){ res += N/443; N /= 443; } return res; } int main() { int _t; cin>>_t; vector<mint> f(1000000); f[0] = 1; for(int i=1;i<f.size();i++){ int v = i; while(v%443==0)v/=443; f[i] = f[i-1] * v; } int T; cin>>T; swap(_t,T); rep(_,_t){ int N,M; cin>>N>>M; if(_==T-1){ cout<<-1<<endl; } else{ mint ans = f[M]; ans /= f[N]; ans /= f[M-N]; ans *= mint(443).pow(get(M)-get(N)-get(M-N)); cout<<ans.val()<<endl; } } }