F. Crossword Expert - 题解

比赛与标签

比赛: Educational Codeforces Round 68 (Rated for Div. 2) 标签: combinatorics, dp, number theory, probabilities, two pointers 难度: *2400

题目大意喵~

主人，你好呀！今天我们来解决一个关于概率论的有趣问题，喵~

题目是这样子的：我们有 n 个填字游戏和总共 T 秒的时间。我们要按顺序一个个地解决这些游戏。对于第 i 个游戏，解决它需要的基础时间是 t_i 秒。但是呢，我们有时候会有点小迷糊，所以实际花费的时间有两种可能：有 1/2 的概率是 t_i 秒，还有 1/2 的概率是 t_i + 1 秒，多花一秒钟。

我们就在这 T 秒钟内不停地做题，直到时间用完或者所有题目都做完为止。如果恰好在 T 秒结束的瞬间完成了一道题，那这道题也算作是完成了哦。

我们的任务是，计算出我们最终能完成的题目数量的期望值。结果需要对 10^9 + 7 取模，呐。

简单来说就是：

• 输入: 题目数量 n，总时间 T，以及每个题目的基础用时 t_1, t_2, ..., t_n。
• 输出: 完成题目数量的期望值，对 10^9 + 7 取模。

解题思路的奇妙旅程~

看到“期望”两个字，是不是有点头大呀？别怕别怕，猫娘我来带你一步步解开它的神秘面纱，喵~

期望的优雅变形

对于一个非负整数的随机变量 X（比如我们完成的题目数量），它的期望 E[X] 有一个非常优雅的计算公式： E[X] = Σ (i * P(X = i)) 这个公式直接算起来可能会很复杂，因为 P(X = i) 不太好求。但是，我们可以把它转换成一个更好算的形式！ E[X] = Σ_{k=1 to n} P(X ≥ k) 这个公式的意思是，期望值等于“至少完成 k 道题”的概率之和。是不是很神奇？想一想，如果你完成了 m 道题，那么你对 P(X ≥ 1), P(X ≥ 2), ..., P(X ≥ m) 都做出了贡献，恰好贡献了 m 次，正好等于 m * P(X = m) 在总和中的体现。

所以，我们的目标就变成了计算 Σ_{i=1 to n} P(我们至少完成了 i 道题)。

概率的组合数学魔法

现在问题变成了：对于每个 i (从 1 到 n)，我们至少完成 i 道题的概率是多少呢？

“至少完成 i 道题”意味着我们要在总时间 T 内完成前 i 道题。 我们来分析一下完成前 i 道题需要的时间：

• 基础时间总和是 S_i = t_1 + t_2 + ... + t_i。
• 在这 i 道题中，假设有 k 道题多花了 1 秒。那么总耗时就是 S_i + k。
• 为了能完成这 i 道题，总耗时必须不大于 T，也就是 S_i + k ≤ T，所以 k ≤ T - S_i。

对于前 i 道题，每道题都有两种可能的时间（t_j 或 t_j+1），总共有 2^i 种等可能的组合。 我们需要计算的是，有多少种组合满足 k ≤ T - S_i。 从 i 道题中选出 k 道多花 1 秒，方案数就是组合数 C(i, k)。 所以，满足条件的总方案数就是 Σ_{k=0 to min(i, T - S_i)} C(i, k)。

因此，至少完成 i 道题的概率就是： P(至少完成 i 题) = (Σ_{k=0 to min(i, T - S_i)} C(i, k)) / 2^i

动态规划与双指针的加速魔法！

现在我们的总期望就是 Σ_{i=1 to n} ( (Σ_{k=0 to min(i, T-S_i)} C(i, k)) / 2^i )。

如果每次都暴力计算这个组合数求和，肯定会超时的说。我们需要一个更快的办法！ 让我们观察一下从 i 推进到 i+1 时，这个求和项会怎么变化。 令 Ways(i, R) = Σ_{k=0 to R} C(i, k)。 我们想从 Ways(i, R_i) 快速得到 Ways(i+1, R_{i+1})，其中 R_i = min(i, T - S_i)。

这里有一个神奇的组合恒等式，基于帕斯卡三角 C(n, k) = C(n-1, k) + C(n-1, k-1)： Σ_{k=0 to R} C(i+1, k) = Σ_{k=0 to R} (C(i, k) + C(i, k-1))= (Σ_{k=0 to R} C(i, k)) + (Σ_{k=0 to R} C(i, k-1))= Ways(i, R) + Ways(i, R-1) 而 Ways(i, R-1) = Ways(i, R) - C(i, R)。 所以，Σ_{k=0 to R} C(i+1, k) = 2 * Ways(i, R) - C(i, R)。

哇！我们找到了一个递推关系！当从 i 题推进到 i+1 题时，我们可以先用这个公式算出 Ways(i+1, R_i)，也就是假设可选的额外时间上限 R 不变的情况下的新方案数。 let new_ways = 2 * ways - C(i, R)

但是，时间上限 R 是会变的！新的上限是 R_{i+1} = min(i+1, T - S_{i+1})。 S_{i+1} = S_i + t_{i+1}，所以 T - S_{i+1} 是越来越小的。这意味着我们的 R 总体上是单调不增的。

这不就是双指针思想嘛！喵~ 我们用一个指针 i 遍历 1 到 n，用另一个指针 R 维护当前组合数求和的上界。 在每一步 i -> i+1：

1. 计算 S_{i+1}。
2. 用递推公式 new_ways = 2 * ways - C(i, R) 计算一个临时的方案数。此时的 R 还是上一轮的 R_i。
3. 计算新的上限 bound = T - S_{i+1}。
4. 调整 R：如果 R > bound，我们就从 new_ways 中减去 C(i+1, R) 并将 R 减一，直到 R == bound。
5. 这样，我们就得到了正确的 Ways(i+1, R_{i+1})，然后计算概率并累加到答案里。

因为 R 指针在整个过程中最多只会从 n 减到 0，所以调整 R 的总操作次数是 O(n) 的。整个算法的时间复杂度就是 O(n) 的啦！

代码实现的喵语解说

下面就是把我们的思路变成代码的时刻啦！

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int maxn = 200000;
const ll mod = 1000000007;

// 预处理阶乘、阶乘逆元、2的幂和2的逆元的幂，方便后面O(1)计算组合数和概率，喵~
ll fact[maxn + 5], invf[maxn + 5], pow2[maxn + 5], pow2inv[maxn + 5];

// 快速幂模板，用来求逆元
ll powmod(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) 
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// O(1) 计算组合数 C(n, k)
ll C(int n, int k) {
    if (k < 0 || k > n) 
        return 0;
    return fact[n] * invf[k] % mod * invf[n - k] % mod;
}

int main() {
    // 预处理阶乘
    fact[0] = 1;
    for (int i = 1; i <= maxn; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    // 预处理阶乘逆元
    invf[maxn] = powmod(fact[maxn], mod - 2, mod);
    for (int i = maxn - 1; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % mod;
    }
    
    // 预处理2的幂
    pow2[0] = 1;
    for (int i = 1; i <= maxn; i++) {
        pow2[i] = pow2[i - 1] * 2 % mod;
    }
    
    // 预处理2的逆元的幂
    ll inv2 = powmod(2, mod - 2, mod);
    pow2inv[0] = 1;
    for (int i = 1; i <= maxn; i++) {
        pow2inv[i] = pow2inv[i - 1] * inv2 % mod;
    }

    ll n, T;
    cin >> n >> T;
    vector<ll> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    ll base = 0; // S_i, 基础时间总和
    ll R = 0;    // 组合数求和的上界 k, min(i, T - S_i)
    ll ways = 1; // Σ C(i, k), 初始时 i=0, k=0, C(0,0)=1
    ll ans = 0;  // 最终的期望值

    // 循环遍历每个题目，计算 P(至少完成 i+1 题)
    for (int i = 0; i < n; i++) {
        base += t[i]; // 累加基础时间
        if (base > T) // 如果基础时间都超过了T，那肯定不可能完成了，直接结束
            break;

        // 这是核心递推！从 i 题的方案数 ways(i, R) 得到 i+1 题在 R 不变时的方案数
        // ways(i+1, R) = 2 * ways(i, R) - C(i, R)
        ways = (2 * ways - C(i, R)) % mod;
        if (ways < 0) ways += mod;

        // 计算新的额外时间上限
        ll bound = T - base;
        
        // 调整R，因为bound变小了，R可能过大，需要减小
        while (R > bound) {
            ways = (ways - C(i + 1, R)) % mod; // 把多余的项减掉
            if (ways < 0) ways += mod;
            R--;
        }
        
        // 这段代码在本次提交中没有用到，因为bound单调不增，R只会减小不会增加
        // 但如果题目条件不同，可能需要增加R
        // while (R < bound && R < i + 1) {
        //     R++;
        //     ways = (ways + C(i + 1, R)) % mod;
        //     if (ways >= mod) ways -= mod;
        // }

        // 计算 P(至少完成 i+1 题) = ways / 2^(i+1)
        ll prob = ways * pow2inv[i + 1] % mod;
        ans = (ans + prob) % mod;
    }

    ans %= mod;
    if (ans < 0) ans += mod;
    cout << ans << endl;

    return 0;
}

复杂度分析的说

• 时间复杂度: O(n) 的说。 我们首先花了 O(maxn) 的时间进行预处理。主循环遍历 n 个题目。循环内部，R 指针的调整是关键。因为 base 单调递增，所以 bound 单调不增，R 指针在整个 for 循环中总共只会减少 O(n) 次。所以，均摊下来每次循环的复杂度是 O(1)。总时间复杂度就是 O(n + maxn)。

• 空间复杂度: O(maxn) 的说。 我们用了几个数组来存储预处理的结果，包括阶乘、逆元等，所以空间复杂度是 O(maxn)。

知识点与总结喵~

这道题真是一场酣畅淋漓的思维冒险呀！它巧妙地融合了多种算法思想，我们来总结一下吧：

1. 期望的线性性质: E[X] = Σ P(X ≥ k) 是解决这类期望问题的关键第一步，它能将问题大大简化。
2. 组合数学: 将问题转化为计数问题，使用组合数 C(n, k) 来表示不同情况的方案数。
3. 动态规划思想: 我们没有独立地计算每个 P(至少完成 i 题)，而是找到了从 i 到 i+1 的递推关系，这是DP的核心思想。
4. 双指针优化: 利用 R 指针的单调性，将每次调整求和上界的操作均摊为 O(1)，是使得整个算法达到线性的点睛之笔。
5. 模运算与预处理: 对于组合计数问题，在模意义下进行计算是常规操作。预处理阶乘和逆元能让我们 O(1) 回答组合数查询，大大提高效率。

希望这次的题解能帮助到你，主人！以后遇到类似的问题，也要像猫娘一样，充满好奇心，一步步揭开它的面纱哦！加油，喵~！