結果
問題 | No.1554 array_and_me |
ユーザー |
|
提出日時 | 2021-07-12 22:54:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,784 bytes |
コンパイル時間 | 1,925 ms |
コンパイル使用メモリ | 171,084 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-02 03:36:59 |
合計ジャッジ時間 | 6,089 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include<bits/stdc++.h>using namespace std;#ifndef ONLINE_JUDGE#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)void err(){cout << "\033[39;0m" << endl;}template<template<typename...> class T,typename t,typename... A>void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}template<typename T,typename... A>void err(T a,A... x){cout << a << ' '; err(x...);}#else#define dbg(...)#endiftypedef long long ll;typedef pair<int,int> pi;typedef vector<int> vi;template<class T> using vc=vector<T>;template<class T> using vvc=vc<vc<T>>;template<class T> void mkuni(vector<T>&v){sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());}template<class T>void print(T x,int suc=1){cout<<x;if(suc==1) cout<<'\n';else cout<<' ';}template<class T>void print(const vector<T>&v,int suc=1){for(int i=0;i<v.size();i++)print(v[i],i==(int)(v.size())-1?suc:2);}#define pb push_back#define lowbit(x) x & -x#define int long longconst int N=2e5+7;const int mod=998244353;ll quick(ll x, ll y) {ll res=1;while(y) {if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;}return res;}int t,n,k;int a[101010];int X[101010];void solve() {auto cmp = [](int L,int R) {return 1LL*a[L]*(X[R]+1)<1LL*a[R]*(X[L]+1);};priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);cin>>n>>k;ll s=0;for(int i=0;i<n;++i) {cin>>a[i];s+=a[i];X[i]=0;pq.push(i);}ll ans=1;for(int i=0;i<k;++i) {int x=pq.top();pq.pop();X[x]++;ans=ans*(1+i)%mod;ans=ans*quick(X[x],mod-2)%mod;ans=ans*a[x]%mod;ans=ans*quick(s,mod-2)%mod;pq.push(x);}print(ans);}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--) solve();}