#677769 (C++14) No.1554 array_and_me

• 問題: No.1554 array_and_me
• ユーザー: jeffxzy
• 提出日時: 2021-07-12 23:26:13
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 1,901 bytes
• コンパイル時間: 1,688 ms
• コンパイル使用メモリ: 170,900 KB
• 実行使用メモリ: 9,216 KB
• 最終ジャッジ日時: 2024-07-02 03:37:11
• 合計ジャッジ時間: 5,466 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 16 WA * 25

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#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)
{
    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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX