CF891E Lust

设每个数被减少了 $b _ i$ 次，考察答案构成的本质，发现答案为 $\prod a _ i - \prod (a _ i - b _ i)$ ，只需要考察 $\prod (a _ i - b _ i)$ 的期望。对于一组确定的 $\{b _ i\}$ ，由于操作的顺序构成的方案数为 $\frac {k!} {\prod b _ i!}$ 。注意到和 $b _ i$ 有关，考虑 EGF 。对于第 $i$ 个数有

$$
\begin {aligned}
F _ i (x) & = \sum _ {i = 0} (a _ i - i) \frac {x ^ i} {i!} \\
& = \sum _ {i = 0} a _ i \frac {x ^ i} {i!} - \sum _ {i = 0} i \frac {x ^ i}{i!} \\
& = a _ i \sum _ {i = 0} \frac {x ^ i} {i!} - x\sum _ {i = 1} i \frac {x ^ {i - 1}}{(i - 1)!} \\
& = a _ i e ^ x - x e ^ x \\
& = (-x + a _ i) e ^ x
\end {aligned}
$$

那么 $ANS = [x ^ k] \prod (-x + a _ i) e ^ x = [x ^ k] e ^ {nx} \prod (-x + a _ i)$ 。分治将后面部分乘起来，得到多项式 $\sum _ {i = 0} ^ n c _ i x ^ i$ 。那么有

$$
\begin {aligned}
ANS & = k! [x ^ k] e ^ {nx} \sum _ {i = 0} ^ n c _ i x ^ i \\
& = k![x ^ k] \sum _ {i = 0} ^ n \frac {n ^ i x ^ i} {i!} \sum _ {i = 0} ^ n c _ i x ^ i \\
& = k! \sum _ {i = 0} ^ n \frac {n ^ i} {i!} c _ {k - i}
\end {aligned}
$$

查看代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef __int128 L;
typedef long long LL;
const int N = 1e5 + 10, p1 = 998244353, p2 = 1004535809, p3 = 469762049, p = 1e9 + 7;
const L mul = (L)p1 * p2 * p3;
int w[N];
template <const int &mod>
struct NTT
{
    int rev[N];
    int binpow (int b, int k = mod - 2)
    {
        int res = 1;
        for (; k; k >>= 1, b = (LL)b * b % mod)
            if (k & 1) res = (LL)res * b % mod;
        return res;
    }
    void ntt (int *x, int bit, int op)
    {
        int tot = 1 << bit;
        for (int i = 0; i < tot; ++i)
            if ((rev[i] = rev[i >> 1] >> 1 | ((i & 1) << bit - 1)) > i)
                swap(x[rev[i]], x[i]);
        for (int mid = 1; mid < tot; mid <<= 1)
        {
            int w1 = binpow(3, (mod - 1) / (mid << 1));
            if (!~op) w1 = binpow(w1);
            for (int i = 0; i < tot; i += mid << 1)
                for (int j = 0, k = 1; j < mid; ++j, k = (LL)k * w1 % mod)
                {
                    int p = x[i | j], q = (LL)k * x[i | j | mid] % mod;
                    x[i | j] = (p + q) % mod, x[i | mid | j] = (p - q) % mod;
                }
        }
        if (~op) return;
        int itot = binpow(tot);
        for (int i = 0; i < tot; ++i)
            x[i] = (LL)x[i] * itot % mod;
    }
    void PolyMul (int n, vector <int> &f, int m, vector <int> &g, int nm, vector <int> &w)
    {
        static int A[N], B[N], C[N];
        for (int i = 0; i <= n; ++i) A[i] = f[i] % mod;
        for (int i = 0; i <= m; ++i) B[i] = g[i] % mod;
        int bit = 1;
        while (n + m + 1 > 1 << bit) ++bit;
        int tot = 1 << bit;
        for (int i = n + 1; i < tot; ++i) A[i] = 0;
        for (int i = m + 1; i < tot; ++i) B[i] = 0;
        ntt(A, bit, 1), ntt(B, bit, 1);
        for (int i = 0; i < tot; ++i)
            C[i] = (LL)A[i] * B[i] % mod;
        ntt(C, bit, -1);
        for (int i = 0; i <= nm; ++i) w[i] = C[i];
    }
};
NTT <p1> q1; NTT <p2> q2; NTT <p3> q3;
int CRT (int x1, int x2, int x3)
{
    L res = 0;
    res += (L)x1 * p2 * p3 * q1.binpow((LL)p2 * p3 % p1);
    res += (L)x2 * p1 * p3 * q2.binpow((LL)p1 * p3 % p2);
    res += (L)x3 * p1 * p2 * q3.binpow((LL)p1 * p2 % p3);
    res %= mul;
    if (res >= (L)p * p * N) res -= mul;
    if (res <= -(L)p * p * N) res += mul;
    return res % p;
}
void solve (int l, int r, int &k, vector <int> &g)
{
    if (l == r) return g[0] = w[l], g[1] = -1, void();
    int mid = l + r >> 1;
    int nm = min(k, r - l + 1), n = min(k, mid - l + 1), m = min(k, r - mid);
    vector <int> A, B, C, D, E;
    A.resize(n + 1); B.resize(m + 1);
    C.resize(nm + 1), D.resize(nm + 1), E.resize(nm + 1);
    solve(l, mid, k, A), solve(mid + 1, r, k, B);
    q1.PolyMul(n, A, m, B, nm, C);
    q2.PolyMul(n, A, m, B, nm, D);
    q3.PolyMul(n, A, m, B, nm, E);
    for (int i = 0; i <= nm; ++i)
        g[i] = CRT(C[i], D[i], E[i]);
}
int binpow (int b, int k = p - 2)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % p)
        if (k & 1) res = (LL)res * b % p;
    return res;
}
int main ()
{
    int n, m;
    read(n, m);
    int tot = 1;
    for (int i = 1; i <= n; ++i)
        read(w[i]), tot = (LL)tot * w[i] % p;
    vector <int> A; A.resize(min(m, n) + 1);
    solve(1, n, m, A);
    int res = 0;
    for (int i = 0, t = 1; i <= min(n, m); t = (LL)t * (m - i++) % p)
        (res += (LL)binpow(n, m - i) * t % p * A[i] % p) %= p;
    write(((tot - (LL)res * binpow(binpow(n, m))) % p + p) % p);
    return 0;
}