結果

問題 No.1554 array_and_me
コンテスト
ユーザー jeffxzy
提出日時 2021-07-12 23:31:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,949 bytes
コンパイル時間 1,662 ms
コンパイル使用メモリ 171,020 KB
実行使用メモリ 9,216 KB
最終ジャッジ日時 2024-07-02 03:37:28
合計ジャッジ時間 5,473 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mod 998244353
#define debug 0
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;


const ll N = 200000 + 5;
const ll MOD = (ll)998244353;
int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘 
void init(){
    inv[1] = 1;
    for(ll i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(ll i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}

ll comb(ll n, ll m){//comb(n, m)就是C(n, m) 
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}

ll qpow(ll a,ll b){
    ll ans=1;
    ll k=a;
    ll m=mod;
    while(b){
        if(b&1)ans=ans*k%m;
        k=k*k%m;
        b>>=1;
    }
    return ans;
}

struct sk
{
	double val;
	ll id;
}p[500005];

double q[500005];

ll g[500005]={0};

bool cmp(sk a,sk b)
{
//	if(a.val==b.val)
		return q[a.id]<q[b.id];
//	return a.val<b.val;
}

int main()
{
	init();
	
	ll t,n,m,i,j,k,used;
	
	cin>>t;
	while(t--)
	{
		cin>>n>>k; 
		
		double sum=0;
		used=k;
		for(i=1;i<=n;i++)
		{
			scanf("%lf",&q[i]);
			sum+=q[i];
		}
//		deb(sum);
		for(i=1;i<=n;i++)
		{
			p[i].val=1.0*(q[i]*k)/sum;
			g[i]=((ll)p[i].val);
			used-=(ll)p[i].val;
			p[i].val-=(ll)p[i].val;
			p[i].id=i;
		}
	
		sort(p+1,p+1+n,cmp);
	
		for(i=n;i>=1;i--)
		{
			if(used==0) break;
			g[p[i].id]++;
			used--;
		}
	
		for(i=1;i<=n;i++) deb(g[i]);
		
		ll finans=1;
//		deb(sum);
		ll sum2=(ll)sum;
		
		for(i=1;i<=n;i++)
		{
			deb(sum2);deb(g[i]); 
			ll pin=q[i]*qpow(sum2,mod-2); pin%=mod;
			ll pout=(sum2-(ll)q[i])*qpow(sum2,mod-2); pout%=mod;
			ll temp=qpow(pin,g[i])*qpow(pout,(k-g[i])); temp%=mod;
			temp=temp*comb(k,g[i]); temp%=mod;
			finans*=temp; finans%=mod;
			sum2-=(ll)q[i];
			k-=(ll)g[i];
			deb(finans);
		}
		
		printf("%lld\n",finans);
	}
	
	return 0;
}
0