CF1842G Tenzing and Random Operations 题解

非常好题目。

我们考虑计算出所有可行的答案最后除以 来计算出答案。

考虑一个简单的 dp 设计。令 表示前 个数进行了 次加法操作所得到的方案数。

转移是每次加入一个数或者直接乘转移到下一个位置。你发现这个复杂度直接爆炸了，因为 的范围是 。

我们希望把状态从 中踢出去。

考虑使用乘法分配律。但是暴力展开之后实际上并不好处理。我们继续观察一下，考虑每次操作对每个位置产生的影响，也就是下面这张表格：

我们最后要算的就是每一行的和乘起来。观察这张表格，我们有一个重要的发现：对于乘法分配律展开之后的每一项，你最多会收到来自 次操作的 的影响。

换句话说，其余的操作具体是在哪个位置开始的，我们并不关心。

因此，我们可以令 表示前 个数进行了 次操作，并且这 次操作的每一次都至少做出了贡献的和。我们需要保证一定做出了贡献，因此我们把每个操作具体落在了哪个位置推迟到这个操作第一次做贡献的时候考虑（也就是所谓的“延迟决策技巧”）。

转移有三种：

• 直接选择 。此时乘上 转移即可。
• 选择之前贡献过的某个 ，此时乘上 转移即可。
• 选择一个新的 。此时我们有 个操作可以进行选择，因为这个元素必须在当前元素之前做出贡献，因此一共有 个可行的位置，此时乘上 转移到下一个位置即可。

最后对于 ，需要乘上 为剩下没有做出贡献的操作选择位置。由于没有做出贡献，其具体在哪个位置我们并不关心，因此可以随便选择。

还有另外一个组合意义的版本可以用来辅助理解。

假设你需要从 走到 。

考虑把 看成“从 走到 有 个不同的道路”。此外你还有 个互不相同的道具，你可以选择一个位置使用这个道具，这个道具会在之后的每个 和 之间额外创造 条道路。

假设你在某些位置使用了某些道具，最后你从 走到 的方案数就是题目中所求的 。

你需要对所有使用道具的情况求出从 走到 的方案数之和。

三种转移可以如下对应：

• 直接选择 。对应走原来的路。
• 选择之前贡献过的某个 。对应选择之前用过的某个道具创造出来的路。
• 选择一个新的 。对应走一个之前放下来，但是从来没有用过的道具创造出来的路。

直接进行这个 dp 复杂度就是 的了。

▶

INFO 参考代码

```cpp

#include

#include

using uint = unsigned int; using ll = long long; using ull = unsigned long long;

namespace maths { template <ull mod, class int_type = ll, class uint_type = ull> class modular { private: uint_type x; void norm() { x -= mod * (x >= mod); }

public: modular() : x(0) {} modular(int_type _x) { if (_x < 0) { x = _x % (int_type)mod + (int_type)mod; } else { x = _x % mod; } norm(); return; } friend modular operator+(const modular &lhs, const modular &rhs) { modular ret; ret.x = lhs.x + rhs.x; ret.norm(); return ret; } friend modular operator-(const modular &lhs, const modular &rhs) { modular ret; ret.x = lhs.x + mod - rhs.x; ret.norm(); return ret; } friend modular operator(const modular &lhs, const modular &rhs) { return modular(lhs.x rhs.x); } modular operator-() const { modular ret; ret.x = mod - x; return ret; } modular operator-=(const modular &b) { return this = this - b; } modular operator+=(const modular &b) { return this = this + b; } modular operator=(const modular &b) { return this = this b; } bool operator==(const modular &b) const { return x == b.x; } uint_type val() const { return x; } friend std::istream &operator>>(std::istream &is, modular &rhs) { is >> rhs.x; rhs.x %= mod; return is; } friend std::ostream &operator<<(std::ostream &os, const modular &rhs) { os << rhs.val(); return os; } };

using modint998244353 = modular<998244353>; using modint1000000007 = modular<1000000007>; } // namespace maths

namespace maths { template T quick_pow(T a, ull b, T id = T()) { T ret = id; for (; b; b >>= 1, a = a * a) { if (b & 1) { ret = a * ret; } } return ret; }

template T quick_pow(T a, const std::string &s, T id = T()) { T ret = id; for (size_t i = 0; i < s.size(); i++, a = a * a) { if (s[i] == ‘1’) { ret = a * ret; } } return ret; }

} // namespace maths

namespace solve { void solve() { using mll = maths::modint1000000007; const uint mod = 1e9 + 7; uint n, m, val; std::cin >> n >> m >> val; std::vector v(n); for (size_t i = 0; i < n; i++) { std::cin >> v[i]; }

std::vector<std::vector<mll>> dp(n + 1, std::vector<mll>(n + 1));  dp[0][0] = 1;  for (size_t i = 0; i < n; i++) {     for (size_t j = 0; j < n; j++) {         if (dp[i][j] == 0) {             continue;         }         dp[i + 1][j] += dp[i][j] * (v[i] + mll(val) * j);         dp[i + 1][j + 1] += dp[i][j] * (i + 1) * mll(m - j) * val;     } }  mll ans = 0; const mll inv_n = maths::quick_pow<mll>(n, mod - 2, 1);  for (size_t i = 0; i <= n; i++) {     ans += maths::quick_pow<mll>(n, m - i, 1) * dp[n][i]; }  ans *= maths::quick_pow<mll>(inv_n, m, 1);  std::cout << ans << std::endl;

} } // namespace solve

int main() { solve::solve(); return 0; }