提出 #28299055

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 1010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b;
ll fc[maxn], nv[maxn], dp[maxn][maxn], x;

ll fxp(ll b, ll e) {
    ll r = 1, k = b;
    while (e != 0) {
        if (e % 2) r = (r * k) % mod;
        k = (k * k) % mod; e /= 2;
    }
    return r;
}

ll inv(ll x) {
    return fxp(x, mod - 2);
}

ll bnm(ll a, ll b) {
    ll i, r = 1;
    if (a < b || b < 0) return 0;
    for (i = a - b + 1; i <= a; i++) r = (r * i) % mod;
    r = (r * nv[b]) % mod;
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    fc[0] = 1; nv[0] = 1;
    for (i = 1; i < maxn; i++) {
        fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    }

    cin >> n >> m;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dp[0][0] = 1;
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= 1) dp[i][j] = (dp[i][j] + a[i] * dp[i - 1][j - 1]) % mod;
        }
    }

    for (i = 0; i <= n; i++) {
        x = dp[n][n - i];
        x = (x * bnm(m, i)) % mod;
        x = (x * fc[i]) % mod;
        x = (x * fxp(n, m - i)) % mod;
        res = (res + x) % mod;
    }

    res = (res * inv(fxp(n, m))) % mod;
    cout << res << nl;

    return 0;
}

提出情報

ジャッジ結果