Editorial for Hikamura, Kỳ thủ cờ tướng

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
const int half = (mod + 1) / 2;

int pw(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) {
            r = 1ll * r * a % mod;
        }
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return r;
}
int inv(int x) {
    return pw(x, mod - 2);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int ntest;
    cin >> ntest;
    while (ntest--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        int s = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            s += a[i];
        }
        int invs = inv(s);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int p = 1ll * a[i] * invs % mod;
            int x = ((1 - 2 * p) % mod + mod) % mod;
            int prob = 1ll * (1 - pw(x, m) + mod) * half % mod;
            ans = (ans + prob) % mod;
        }
        cout << 1ll * (ans + m) * half % mod << endl;
    }

    return 0;
}

Comments

Please read the guidelines before commenting.

There are no comments at the moment.