CodeForces 1737 E - Ela Goes Hiking 题解

· · 题解

更好的阅读体验。

思路

我们先将题目看成 n 个点的问题。

首先我们知道，如果一个点初始方向是向右，那么他无论如何都不可能活到最后。

所以我们只需要考虑向左的情况。

我们可以求出它初始方向向左时活到最后的方案数，然后除于所有的方案，就是我们要求的概率了，接下来我们考虑如何求出活到最后的方案数。

我们可以将整个过程分为两部分，首先向左走到底，此时右边的无论如何变化都不会影响到当前左边的部分，然后再转向向右。

设当前点为 i，对于左边的部分，如果有一个点的编号大于 \lfloor\frac{i}{2}\rfloor 并且它的初始方向向右，则当前节点一定会被这个节点吃掉。

所以编号大于 \lfloor\frac{i}{2}\rfloor 的点的初始方向都要向右，所以左边一共有 2^{\lfloor\frac{i}{2}\rfloor} 种方案。

再考虑右边的部分，我们设当前的方案数为 f_i（不考虑左边的部分），则如果对于所有小于 2\cdot i 的点的方向全部向右，则说明当前节点一定会被吃掉（如果最后一个点向右，那么在吞掉别人之前一定会碰到墙回头，所以可以看成向左），为了防止当前节点被吃掉，则无论如何在小于 2\cdot i 的节点中有向左的，我们便可以写出关于 f_i 的式子：

f_i = \sum_{j=i+1}^{2\cdot i} f_j

可以用前缀和优化到 O(n) 的时间复杂度。

然后将左边和右边的方案数乘起来，在除于所有的方案数，就是答案了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
int T, n;
LL f[3000005], g[3000005];
LL Pow(LL a, LL b) {
    LL s = 1;
    while (b) {
        if (b & 1)
            s = s * a % MOD;
        a = a * a % MOD, b = b >> 1;
    }
    return s;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= 2 * n; i++)
            f[i] = g[i] = 0;
        f[n] = g[n] = 1;
        for (int i = n - 1; i; i--)
            f[i] = (g[i + 1] - g[i * 2] + MOD) % MOD, g[i] = (g[i + 1] + f[i]) % MOD;
        for (int i = 1; i <= n; i++)
            printf("%lld\n", f[i] * Pow(2, i / 2) % MOD * Pow(Pow(2, n - 1), MOD - 2) % MOD);
    }
    return 0;
}