CF1842G Tenzing and Random Operations 题解

Description

有一长度为 nn 的序列 aa 和一整数 vv，对该序列进行 mm 次操作。

每次操作中，等概率地随机选择一整数 i∈[1,n]i \in [1, n]，对所有的 j∈[i,n]j \in [i, n]，赋值 aj←aj+va_j \gets a_j+v，求出 mm 次操作后 Πi=1nai\Pi_{i=1}^n a_i 的期望值，对 109+710^9+7 取模。

数据范围：0≤n≤50000\leq n \leq 5000，1≤m,v≤1091 \leq m, v \leq10^9，ai∈[1,109]∩Za_i \in [1, 10^9] \cap \mathbb{Z}。

Solution

设 bib_i 表示第 ii 次操作随机选择的数，那么答案形如：

∏i=1n(ai+∑j=1m[bj≤i]v)\prod_{i=1}^{n}{\left(a_i+\sum_{j=1}^{m}{\left[b_j\leq i\right]v}\right)}

这个东西显然是可以拆开的，最终答案一定形如一些 aia_i 的乘积和某些 [bj≤i]v[b_j\leq i]v 的乘积。

假设 [bj≤i]v[b_j\leq i]v 选的下标是 i1<i2<…<iki_1<i_2<\ldots<i_k，如果 bj>i1b_j>i_1，则乘积为 00，没有贡献。否则一定有贡献，所以选的 bjb_j 只需要满足 bjb_j 不超过第一个选 jj 的下标即可。

这样就可以 dp 了。

设 fi,jf_{i,j} 表示 [1,i][1,i] 的前缀，目前已经选好了 jj 的 bkb_k 的位置。如果这一位选了 aia_i，则 fi,j←aifi−1,jf_{i,j}\leftarrow a_if_{i-1,j}。如果这一位选了之前选过的 bkb_k，则 fi,j←jvfi−1,jf_{i,j}\leftarrow jvf_{i-1,j}。如果这一位选了一个新的 bkb_k，则 fi,j+1←(m−j)iv⋅fi−1,jf_{i,j+1}\leftarrow (m-j)iv\cdot f_{i-1,j}，这里的 ii 是从 [1,i][1,i] 中选一个作为 bkb_k 的方案数。

最终答案即为 ∑fn,inm−inm\sum \frac{f_{n,i}n^{m-i}}{n^m}。

时间复杂度：O(n2)O(n^2)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e3 + 5, kMod = 1e9 + 7;

int n, m, v;
int a[kMaxN], f[kMaxN][kMaxN];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void dickdreamer() {
  std::cin >> n >> m >> v;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= std::min(n, m); ++j) {
      inc(f[i][j], 1ll * a[i] * f[i - 1][j] % kMod);
      inc(f[i][j], 1ll * j * v % kMod * f[i - 1][j] % kMod);
      inc(f[i][j + 1], 1ll * (m - j) * i % kMod * v % kMod * f[i - 1][j] % kMod);
    }
  }
  int ans = 0;
  for (int i = 0; i <= std::min(n, m); ++i)
    inc(ans, 1ll * f[n][i] * qpow(n, m - i) % kMod);
  std::cout << 1ll * ans * qpow(qpow(n), m) % kMod << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
CF1842G Tenzing and Random Operations 题解
https://sobaliuziao.github.io/2024/10/02/post/64110978.html
作者
Egg_laying_master
发布于
2024年10月2日
许可协议