CodeForces 1737 E

CodeForces 1737 E"/>

CodeForces 1737 E

思路

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

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

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

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

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

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

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

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

f i = ∑ j = i + 1 2 ⋅ i f j f_i = \sum_{j=i+1}^{2\cdot i} f_j fi​=j=i+1∑2⋅i​fj​

可以用前缀和优化到 O ( n ) O(n) 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;
}