Codeforces

Luogu

分析

设最后得到的序列为 $\{b\}$，可以发现答案为
$$
\prod_{i = 1}^n a_i - \prod_{i = 1}^n b_i
$$
前面的容易计算，考虑计算后面的期望值。不妨将其乘上 $n ^ k$，变为计算所有方案的和。

可以想到使用 EGF 来求解。设
$$
F_i(x) = \sum_{j \geq 0} (a_i - j) x^j = (a_i - x) e^x
$$
则所有方案的 $\prod b_i$ 的和为
$$
k! [x^k] \prod_{i = 1}^n F_i(x) = k! [x^k] e^{nx} \prod_{i = 1}^n (a_i - x)
$$
求出 $\prod(a_i - x)$，然后枚举其次数计算即可。时间复杂度 $\mathcal{O}(n \log^2 n)$ 甚至 $\mathcal{O}(n^2)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 5000 + 10;
const int mod = 1e9 + 7;
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int n, k, a[N], F[N], pw[N];

int main() {
    n = read(), k = read(); int s = 1;
    for (int i = 1; i <= n; ++i) a[i] = read(), s = 1ll * s * a[i] % mod;
    F[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j; --j)
            F[j] = (1ll * F[j] * a[i] - F[j - 1] + mod) % mod;
        F[0] = 1ll * F[0] * a[i] % mod;
    }
    pw[0] = 1;
    for (int i = 1; i <= min(n, k); ++i) pw[i] = 1ll * pw[i - 1] * (k - i + 1) % mod;
    int ans = 0;
    for (int i = 0; i <= min(n, k); ++i)
        ans = (ans + 1ll * F[i] * qpow(n, k - i) % mod * pw[i]) % mod;
    ans = 1ll * ans * qpow(n, 1ll * k * (mod - 2) % (mod - 1)) % mod;
    ans = (s - ans + mod) % mod;
    printf("%d\n", ans);
    return 0;
}