結果
問題 |
No.1554 array_and_me
|
ユーザー |
|
提出日時 | 2021-06-18 22:25:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 740 ms |
コンパイル使用メモリ | 80,092 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 20:51:07 |
合計ジャッジ時間 | 3,008 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 9 | main() | ^~~~
ソースコード
#include<iostream> #include<queue> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; int T,N,K; int A[1<<17]; mint inv[1<<17]; main() { cin>>T; inv[1]=1; for(int i=2;i<1<<17;i++)inv[i]=-(998244353/i)*inv[998244353%i]; for(;T--;) { cin>>N>>K; int sum=0; priority_queue<pair<double,pair<int,int> > >P; for(int i=0;i<N;i++) { cin>>A[i]; P.push(make_pair(A[i],make_pair(0,A[i]))); sum+=A[i]; } mint ans=1,invsum=mint(1)/sum; for(int i=1;i<=K;i++) { ans*=i; pair<double,pair<int,int> >p=P.top();P.pop(); p.second.first--; p.first=p.second.second/(double)(1-p.second.first); P.push(p); ans*=inv[-p.second.first]; ans*=p.second.second*invsum; } cout<<ans.val()<<endl; } }