結果

問題 No.1554 array_and_me
ユーザー jeffxzyjeffxzy
提出日時 2021-07-12 23:28:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,943 bytes
コンパイル時間 1,565 ms
コンパイル使用メモリ 170,320 KB
実行使用メモリ 16,340 KB
最終ジャッジ日時 2023-09-14 20:46:40
合計ジャッジ時間 5,602 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
11,276 KB
testcase_01 AC 36 ms
11,332 KB
testcase_02 AC 35 ms
11,284 KB
testcase_03 AC 36 ms
11,288 KB
testcase_04 AC 35 ms
11,280 KB
testcase_05 AC 36 ms
11,300 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 67 ms
16,080 KB
testcase_12 AC 66 ms
16,212 KB
testcase_13 AC 66 ms
16,216 KB
testcase_14 AC 66 ms
16,164 KB
testcase_15 AC 65 ms
16,340 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 67 ms
11,284 KB
testcase_37 AC 66 ms
11,292 KB
testcase_38 AC 66 ms
11,324 KB
testcase_39 AC 66 ms
11,284 KB
testcase_40 AC 66 ms
11,412 KB
testcase_41 AC 37 ms
11,292 KB
権限があれば一括ダウンロードができます

ソースコード

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