NekoNowcoder

Appearance

白树台学园 (easy version) - 题解 ​

标签与难度 ​

标签: 期望, 概率, 数学, 线性DP, 前缀和优化, 逆元 难度: 2100

题目大意喵~ ​

哈喵~ 各位看官，今天我们来解决一道关于期望的有趣问题，喵！

事情是这样的：我们有一个长度为 nn 的队伍，每个位置上的人都有一个擅长的方面（可以看作是颜色），总共有 mm 种不同的方面。有些位置上的人选是固定的，他们的颜色 aia_i 是一个 11 到 mm 之间的确定值。但其他位置的人选还没定，用 00 表示，这些位置的颜色会从 11 到 mm 中等概率随机选择一个。

红方会随机攻击我们队伍的一个连续区间 [l,r][l, r]。一个区间的“牢固度”被定义为这个区间内不同颜色的数量。

我们的任务是，计算在所有可能的随机颜色选择和所有可能的随机区间选择下，区间牢固度的期望值是多少。结果需要对 998244353998244353 取模，呐。

举个栗子：如果队伍是 [1, 0, 2]，m=2m=2。位置 22 的颜色可能是 11 或 22 (概率各 1/21/2)。

  • 如果是 [1, 1, 2]，随机区间的牢固度期望是...
  • 如果是 [1, 2, 2]，随机区间的牢固度期望是... 我们要计算的是这两个情况的平均值，喵~

解题思路分析 ​

这道题看起来有点复杂，因为它混合了两种随机性：颜色的随机选择和区间的随机选择。不过别怕，我带你一步步拆解它，的说！

核心思想：期望的线性性质 ​

首先，我们要计算的是期望值。对付期望问题，有一个超级好用的法宝，那就是期望的线性性质！

E[X+Y]=E[X]+E[Y]E[X+Y] = E[X] + E[Y]

一个区间的牢固度（不同颜色数）可以看作是“颜色1是否出现”+“颜色2是否出现”+...+“颜色m是否出现”的总和。其中，如果颜色 cc 出现，值为1，否则为0。

根据期望的线性性质，一个区间的期望牢固度就是：

E[区间不同颜色数]=∑c=1mP(颜色 c 在该区间出现)E[\text{区间不同颜色数}] = \sum_{c=1}^{m} P(\text{颜色 } c \text{ 在该区间出现})

我们的目标是求在所有 n(n+1)2\frac{n(n+1)}{2} 个区间上的期望牢固度的平均值。设 EtotalE_{total} 为我们要求的最终答案。

Etotal=1n(n+1)2∑1≤l≤r≤nE[区间 [l,r] 的不同颜色数]E_{total} = \frac{1}{\frac{n(n+1)}{2}} \sum_{1 \le l \le r \le n} E[\text{区间 }[l, r] \text{ 的不同颜色数}]

把上面的公式代入，并交换求和顺序，我们得到：

Etotal=1n(n+1)2∑1≤l≤r≤n∑c=1mP(c 在 [l,r] 出现)E_{total} = \frac{1}{\frac{n(n+1)}{2}} \sum_{1 \le l \le r \le n} \sum_{c=1}^{m} P(c \text{ 在 } [l, r] \text{ 出现})

Etotal=1n(n+1)2∑c=1m∑1≤l≤r≤nP(c 在 [l,r] 出现)E_{total} = \frac{1}{\frac{n(n+1)}{2}} \sum_{c=1}^{m} \sum_{1 \le l \le r \le n} P(c \text{ 在 } [l, r] \text{ 出现})

这个式子告诉我们，可以对每一种颜色 cc 单独计算它对总期望的贡献，最后加起来！是不是清晰多啦？

转换思路：正难则反 ​

直接计算“出现”的概率有点麻烦，因为它可能在多个位置出现。我们不如换个角度，计算它“不出现”的概率，然后用 11 去减。这可是我的得意技之一哦，喵~

P(c 在 [l,r] 出现)=1−P(c 在 [l,r] 不出现)P(c \text{ 在 } [l, r] \text{ 出现}) = 1 - P(c \text{ 在 } [l, r] \text{ 不出现})

代入上面的总和式：

∑c=1m∑1≤l≤r≤n(1−P(c 在 [l,r] 不出现))\sum_{c=1}^{m} \sum_{1 \le l \le r \le n} (1 - P(c \text{ 在 } [l, r] \text{ 不出现}))

=∑c=1m(n(n+1)2−∑1≤l≤r≤nP(c 在 [l,r] 不出现))= \sum_{c=1}^{m} \left( \frac{n(n+1)}{2} - \sum_{1 \le l \le r \le n} P(c \text{ 在 } [l, r] \text{ 不出现}) \right)

=m⋅n(n+1)2−∑c=1m∑1≤l≤r≤nP(c 在 [l,r] 不出现)= m \cdot \frac{n(n+1)}{2} - \sum_{c=1}^{m} \sum_{1 \le l \le r \le n} P(c \text{ 在 } [l, r] \text{ 不出现})

所以，最终的期望值 EtotalE_{total} 就是：

Etotal=m−1n(n+1)2∑c=1m∑1≤l≤r≤nP(c 在 [l,r] 不出现)E_{total} = m - \frac{1}{\frac{n(n+1)}{2}} \sum_{c=1}^{m} \sum_{1 \le l \le r \le n} P(c \text{ 在 } [l, r] \text{ 不出现})

现在，问题转化为了计算所有颜色在所有区间内不出现的概率之和。

计算“不出现”的概率 ​

对于一个固定的颜色 cc 和一个区间 [l,r][l, r]：

  • 如果区间内某个位置 ii 的颜色已经确定为 cc (即 ai=ca_i = c)，那么 cc 必然出现，不出现的概率为 00。
  • 如果区间内没有确定为 cc 的位置，那么对于每个 ai≠ca_i \neq c 且 ai≠0a_i \neq 0 的位置，它肯定不是 cc。对于每个 ai=0a_i = 0 的位置，它不是 cc 的概率是 m−1m\frac{m-1}{m}。

所以，如果一个区间 [l,r][l, r] 内没有固定的颜色 cc，并且有 kk 个 00，那么 cc 在这个区间不出现的概率就是 (m−1m)k(\frac{m-1}{m})^k。

分段计算与前缀和优化 ​

对于每种颜色 cc，那些 ai=ca_i=c 的位置就像一道道屏障，把整个序列 1...n 分割成了好几个独立的段。一个区间 [l,r][l,r] 如果想要 cc 不出现，它必须完整地落在一个由这些屏障分割出的段里。

例如，如果 n=10n=10，颜色 cc 出现在位置 33 和 88，那么有效的段就是 [1,2][1, 2], [4,7][4, 7], [9,10][9, 10]。我们需要对这些段分别计算贡献。

设一个段为 [start, end]。我们要计算：

Sseg=∑start≤l≤r≤end(m−1m)zeros(l,r)S_{seg} = \sum_{start \le l \le r \le end} \left(\frac{m-1}{m}\right)^{\text{zeros}(l, r)}

其中 zeros(l,r)\text{zeros}(l, r) 是区间 [l,r][l, r] 中 00 的数量。

直接暴力计算这个和是 O((end−start)2)O((end-start)^2) 的，对于所有颜色和所有段，总复杂度会是 O(nm)O(nm) 左右，太慢了喵！必须优化！

我们可以用前缀和来加速这个计算。设 P=m−1mP = \frac{m-1}{m}。 令 pi=Pp_i = P 如果 ai=0a_i=0，否则 pi=1p_i=1。 那么 (m−1m)zeros(l,r)=∏k=lrpk(\frac{m-1}{m})^{\text{zeros}(l, r)} = \prod_{k=l}^r p_k。

令 gi=∏k=1ipkg_i = \prod_{k=1}^i p_k 为 pkp_k 的前缀积。那么 ∏k=lrpk=gr⋅(gl−1)−1\prod_{k=l}^r p_k = g_r \cdot (g_{l-1})^{-1}。 我们要计算的和变成了：

Sseg=∑r=startend∑l=startrgr⋅(gl−1)−1=∑r=startendgr(∑l=startr(gl−1)−1)S_{seg} = \sum_{r=start}^{end} \sum_{l=start}^{r} g_r \cdot (g_{l-1})^{-1} = \sum_{r=start}^{end} g_r \left( \sum_{l=start}^{r} (g_{l-1})^{-1} \right)

这个形式依然需要 O((end−start)2)O((end-start)^2)。但我们可以进一步优化！ 我们可以在 O(n)O(n) 的时间内预处理出以下三个前缀和数组：

  1. prod_g[i] = g_i (前缀积)
  2. sum_inv_g[i] = \sum_{k=0}^{i} (g_k)^{-1} (前缀积的逆元的前缀和)
  3. sum_g_times_sum_inv_g[i] = \sum_{k=1}^{i} g_k \cdot \text{sum\_inv\_g}[k-1]

有了这些，对于任何一个段 [start, end]，我们想求的 ∑r=startendgr(∑j=start−1r−1(gj)−1)\sum_{r=start}^{end} g_r \left( \sum_{j=start-1}^{r-1} (g_j)^{-1} \right) 就可以通过差分在 O(1)O(1) 内算出啦！

∑r=startendgr(sum_inv_g[r−1]−sum_inv_g[start−2])\sum_{r=start}^{end} g_r (\text{sum\_inv\_g}[r-1] - \text{sum\_inv\_g}[start-2])

=∑r=startendgr⋅sum_inv_g[r−1]−sum_inv_g[start−2]⋅∑r=startendgr= \sum_{r=start}^{end} g_r \cdot \text{sum\_inv\_g}[r-1] - \text{sum\_inv\_g}[start-2] \cdot \sum_{r=start}^{end} g_r

第一个部分是 sum_g_times_sum_inv_g 的区间和，第二个部分是 prod_g 的区间和（需要另一个前缀和数组）乘以一个常数。这样，每个段的计算就是 O(1)O(1) 的了！

最终算法流程 ​

  1. 预处理：

    • 计算模逆元，特别是 m−1m^{-1} 和 P=(m−1)m−1(modM)P = (m-1)m^{-1} \pmod{M}。
    • 遍历数组 aa，计算出我们需要的几个前缀和数组。总时间 O(n)O(n)。
    • 记录下每种颜色 cc 出现的所有位置。时间 O(n)O(n)。

  2. 计算总和：

    • 初始化总的不出现概率和 total_complement_prob_sum = 0。
    • 对每种颜色 cc 从 11 到 mm：
      • 取出 cc 的所有固定位置，在列表前后加上 00 和 n+1n+1 作为哨兵。
      • 遍历这些位置，得到一个个不包含固定 cc 的段 [start, end]。
      • 利用预处理好的前缀和数组，在 O(1)O(1) 时间内计算出这个段的贡献，累加到 total_complement_prob_sum。

  3. 得出答案：

    • 总的不出现概率和已经得到。
    • 根据公式 Etotal=m−total_complement_prob_sum⋅(n(n+1)2)−1(modM)E_{total} = m - \text{total\_complement\_prob\_sum} \cdot (\frac{n(n+1)}{2})^{-1} \pmod{M} 计算最终答案。

总时间复杂度是 O(n+m+总固定位置数)=O(n+m)O(n + m + \text{总固定位置数}) = O(n+m)，空间复杂度是 O(n+m)O(n+m)。这下就可以轻松跑过啦，喵~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦！

cpp
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// 定义一个好用的长整型别名
using ll = long long;

// 模数
const int MOD = 998244353;

// 快速幂函数，用来计算 a^b % MOD
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模块逆元函数，a^{-1} mod m = a^{m-2} mod m
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 封装一个加法，防止溢出
void add(ll &a, ll b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

// 封装一个减法，防止变负数
void sub(ll &a, ll b) {
    a -= b;
    if (a < 0) a += MOD;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    vector<vector<int>> color_positions(m + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] != 0) {
            color_positions[a[i]].push_back(i);
        }
    }

    // P 是随机位置的颜色不是某个特定颜色的概率
    ll P = (m - 1) * modInverse(m) % MOD;

    // --- 开始预处理四个关键的前缀和数组 ---
    
    // g[i] = prefix product of p_k, where p_k=P if a[k]=0, else 1
    vector<ll> g(n + 1, 1);
    // sum_g[i] = prefix sum of g_k
    vector<ll> sum_g(n + 1, 0);
    // inv_g[i] = g[i]的逆元
    vector<ll> inv_g(n + 1, 1);
    // sum_inv_g[i] = prefix sum of inv_g[k]
    vector<ll> sum_inv_g(n + 2, 0); // size n+2 for easier indexing sum_inv_g[l-2]
    // sum_g_x_sum_inv_g[i] = prefix sum of g[k] * sum_inv_g[k-1]
    vector<ll> sum_g_x_sum_inv_g(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        g[i] = g[i - 1];
        if (a[i] == 0) {
            g[i] = (g[i] * P) % MOD;
        }
        sum_g[i] = (sum_g[i - 1] + g[i]) % MOD;
        inv_g[i] = modInverse(g[i]);
        sum_inv_g[i+1] = (sum_inv_g[i] + inv_g[i]) % MOD; // sum_inv_g[i] stores sum up to i-1
    }
    sum_inv_g[0] = 1; // g[0] = 1, inv_g[0] = 1

    for (int i = 1; i <= n; ++i) {
        ll term = (g[i] * sum_inv_g[i]) % MOD; // g[i] * sum(inv_g[k] for k=0..i-1)
        sum_g_x_sum_inv_g[i] = (sum_g_x_sum_inv_g[i-1] + term) % MOD;
    }

    ll total_complement_sum = 0;

    // 对每种颜色计算贡献
    for (int c = 1; c <= m; ++c) {
        int last_pos = 0;
        // 把 N+1 也作为一个屏障
        color_positions[c].push_back(n + 1);

        for (int pos : color_positions[c]) {
            int start = last_pos + 1;
            int end = pos - 1;

            if (start <= end) {
                // 利用预处理的前缀和 O(1) 计算段贡献
                // sum_{r=start to end} g[r] * (sum_inv_g[r-1] - sum_inv_g[start-2])
                ll term1 = sum_g_x_sum_inv_g[end];
                sub(term1, sum_g_x_sum_inv_g[start - 1]);

                ll term2_factor = sum_inv_g[start - 1 + 1]; // sum up to start-2
                ll term2_sum = sum_g[end];
                sub(term2_sum, sum_g[start - 1]);
                ll term2 = (term2_factor * term2_sum) % MOD;
                
                ll segment_sum = term1;
                sub(segment_sum, term2);

                add(total_complement_sum, segment_sum);
            }
            last_pos = pos;
        }
    }

    // 总区间数
    ll total_intervals = (ll)n * (n + 1) / 2 % MOD;
    ll inv_total_intervals = modInverse(total_intervals);

    // 计算补集的期望贡献
    ll complement_expectation = (total_complement_sum * inv_total_intervals) % MOD;

    // 最终答案 E = m - E_complement
    ll final_ans = m;
    sub(final_ans, complement_expectation);

    cout << final_ans << endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N+M)O(N + M)

    • 预处理所有前缀和数组需要遍历一次序列，复杂度为 O(N)O(N)。
    • 记录每种颜色的位置需要遍历一次序列，复杂度为 O(N)O(N)。
    • 对每种颜色 c∈[1,M]c \in [1, M]，我们遍历其固定的位置。由于每个位置最多属于一种颜色，所有颜色固定位置的总数最多为 NN。所以遍历所有段的总时间是 O(M+N)O(M + N)。
    • 因此，总的时间复杂度是 O(N+M)O(N+M)，非常高效！

  • 空间复杂度: O(N+M)O(N + M)

    • 我们需要几个长度为 NN 的前缀和数组，空间为 O(N)O(N)。
    • color_positions 向量存储所有固定颜色的位置，总大小为 O(N)O(N)。如果 MM 很大且固定位置很少，也需要 O(M)O(M) 的空间来初始化这个向量。所以总空间是 O(N+M)O(N+M)。

知识点总结 ​

这道题是一道非常棒的期望题，它教会了我们几件重要的事情，喵~

  1. 期望的线性性质: 这是解决复杂期望问题的最有力武器！将整体期望拆解为各个独立事件的概率之和，能极大地简化问题。
  2. 正难则反 (补集思想): 当直接计算“至少一个”很困难时，尝试计算“一个都没有”的概率，然后用总概率 11 去减，往往能柳暗花明。
  3. 前缀和优化: 对于需要反复计算区间和的问题，预处理前缀和（或前缀积、更复杂的前缀信息）是王道！本题中，通过巧妙地设计和预处理多个前缀和数组，我们将 O(N2)O(N^2) 的区间计算降至 O(1)O(1)，是解题的关键。
  4. 分段处理: 当序列中某些特殊点（本题中的固定颜色位置）会影响计算时，可以将序列按这些点分段，在段内进行计算，化整为零。

希望这篇题解能帮助你更好地理解这道题目！如果还有问题，随时可以再来问我哦，喵~