結果
問題 | No.1554 array_and_me |
ユーザー |
![]() |
提出日時 | 2024-08-07 02:37:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 2,215 bytes |
コンパイル時間 | 1,805 ms |
コンパイル使用メモリ | 134,240 KB |
実行使用メモリ | 12,092 KB |
最終ジャッジ日時 | 2024-08-07 02:37:47 |
合計ジャッジ時間 | 6,497 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#include<atcoder/modint>using mint = atcoder::modint998244353;// using mint = long double;#include<math.h>#include<queue>void solve(){ll n,k;cin>>n>>k;vector<ll> a(n);for(int i = 0;i<n;i++) cin>>a[i];ll sum = 0;for(int i = 0;i<n;i++) sum += a[i];vector<ll> use(n),res(n);for(int i = 0;i<n;i++) {use[i] = (a[i]*k) / sum;res[i] = (a[i]*k) % sum;}vector<int> idx(n);for(int i = 0;i<n;i++) idx[i] = i;sort(idx.begin(),idx.end(),[&](int i,int j){if(res[i]!=res[j]) return res[i] > res[j];return a[i] > a[j];});ll now = 0;for(int i = 0;i<n;i++) now += use[i];now = k - now;for(int i = 0;i<now;i++){int ni = idx[i];use[ni]++;}for(int i = 0;i<n;i++) use[i] = 0;using dat = pair<long double,int>;priority_queue<dat> que;vector<long double> f(k+4,0);for(int i = 1;i<=k+3;i++) f[i] = f[i-1] + log(i);auto add = [&](int i) {long double nxt = (use[i]+1) * log(a[i]) - (use[i]+1) * log(sum) - f[use[i]+1];long double now = use[i] * log(a[i]) - use[i] * log(sum) - f[use[i]];que.push(make_pair(nxt - now,i));};for(int i = 0;i<n;i++) add(i);for(int i = 0;i<k;i++){auto now = que.top();que.pop();int ni = now.second;//cout<<now.first<<" "<<ni<<endl;use[ni]++;add(ni);}mint ans = 1;ll all = k;vector<mint> fac(k+1,0);fac[0] = 1;for(int i = 1;i<=k;i++) fac[i] = fac[i-1] * i;ans = fac[k];for(int i = 0;i<n;i++){mint tmp = fac[use[i]].inv();mint p = mint(a[i]) * (mint(sum).inv());p = p.pow(use[i]);// mint tmp = 1. / fac[use[i]];// mint p = (long double) a[i] / sum;// p = pow(p,use[i]);ans *= tmp * p;}cout<<ans.val()<<endl;return;for(int i = 0;i<n;i++) cout<<use[i]<<" ";cout<<endl;}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int t;cin>>t;while(t--){solve();}}