526互联

CF1842G Tenzing and Random Operations 题解

发布时间 2023-10-10 20:26:42作者: User-Unauthorized

题意

给定一个长度为 \(n\) 的正整数序列 \(a\)，对该序列进行 \(m\) 次操作，定义每次操作如下：

从 \(\left[1, n\right]\) 中等概率选取一个 \(i\)，对于 \(j \in \left[i, n\right]\)，执行操作 \(a_j \leftarrow a_j + v\)，其中 \(v\) 是给定的常数。

求 \(m\) 次操作后 \(\displaystyle\prod\limits_{i = 1}^{n}a_i\) 的期望，对 \(10^9 + 7\) 取模。

（\(0 \le n \le 5000，1 \le m,v,a_i \le 10^9\)）。

题解

转化为求全部方案的和。

发现对于任意方案，最终求的式子都形如 \(\prod(a_i + v + v + \cdots)\)，根据乘法分配律，可以发现每一个整式会有一项产生贡献，若这个整式产生贡献的为一个 \(v\)，那么这就代表着一定钦定了一个操作选取了 \([1, i]\) 中的点，具体的说，其贡献有如下三类：

  1. 选取 \(a_i\) 产生贡献；

  2. 选取一个已经钦定了的操作产生的 \(v\)；

  3. 钦定一个新的操作并选取其产生的 \(v\)。

故可以进行 \(\tt{DP}\)，设 \(f_{i, j}\) 表示在 \([1, i]\) 中钦定了 \(j\) 个操作的贡献和，那么有如下转移：

  1. 在这个整式中选取了 \(a_i\)，有 \(f_{i, j} \leftarrow a_i \times f_{i - 1, j}\)；

  2. 在这个整式中选取了一个已经钦定了的操作产生的 \(v\)，枚举产生选取的 \(v\) 的那个操作，有 \(f_{i, j} \leftarrow j \cdot v \times f_{i - 1, j}\)；

  3. 钦定一个新的操作并选取其产生的 \(v\)，首先考虑从所有未钦定的 \(m - j + 1\) 个操作中选取一个，接下来考虑将其钦定为 \([1, i]\) 中的哪个点，有 \(f_{i, j} \leftarrow (m - j + 1) \cdot i \cdot v \times f_{i - 1, j - 1}\)。

那么整个过程中最多钦定 \(\min\left\{n, m\right\}\) 个操作，对于未钦定的操作，由于其未产生贡献，故可以随便选取端点，通过枚举钦定的操作的数量，可以得到答案为

\[\dfrac{\sum\limits_{i = 0}^{\min\left\{n, m\right\}}f_{n, i} \times n^{m - i}}{n^m} \]

总复杂度 \(\mathcal{O}(n \times \min\left\{n, m\right\})\)，可以通过本题。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

constexpr valueType MOD = 1e9 + 7;

void Inc(valueType &a, valueType b) {
    a = a + b;

    if (a >= MOD)
        a -= MOD;
}

valueType sum(valueType a, valueType b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

valueType mul(valueType a, valueType b) {
    return (long long) a * b % MOD;
}

void Mul(valueType &a, valueType b) {
    a = (long long) a * b % MOD;
}

valueType pow(valueType a, valueType b) {
    valueType result = 1;

    while(b > 0) {
        if (b & 1)
            Mul(result, a);

        Mul(a, a);
        b = b >> 1;
    }

    return result;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M, V;

    std::cin >> N >> M >> V;

    ValueVector A(N + 1);

    for(valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    valueType const K = std::min(N, M);

    ValueMatrix F(N + 1, ValueVector(K + 1, 0));

    F[0][0] = 1;

    for(valueType i = 1; i <= N; ++i) {
        for(valueType j = 0; j <= K; ++j) {
            Inc(F[i][j], mul(F[i - 1][j], A[i]));
            
            Inc(F[i][j], mul(F[i - 1][j], mul(j, V)));

            if (j > 0)
                Inc(F[i][j], mul(F[i - 1][j - 1], mul(mul(M - j + 1, i), V)));
        }
    }

    valueType ans = 0;

    for(valueType i = 0; i <= K; ++i)
        Inc(ans, mul(F[N][i], pow(N, M - i)));
    
    ans = mul(ans, pow(pow(N, M), MOD - 2));

    std::cout << ans << std::endl;

    return 0;
}