题解 CF1737E【Ela Goes Hiking】

周子衡 · 2022-10-11 21:33:56 · 题解

手动模拟一下整个过程。不难发现：

• 每只向左的蚂蚁一定会先吃掉初始时它面前连续的右向蚂蚁。特别地，最右边那只蚂蚁一开始的方向是无关紧要的，即使它一开始向右，最后也会转到左边；我们不妨认为这只蚂蚁一定向左。
• 在上面的过程结束后，数轴上还剩下若干只大蚂蚁，每只蚂蚁对应原来一只向左的蚂蚁和若干只（被吃掉）的向右的蚂蚁，称它们构成一个 连续段。接下来这些蚂蚁会依次 决战：第 1 只大蚂蚁和第 2 只大蚂蚁决战，胜者和第 3 只大蚂蚁决战，胜者再和第 4 只大蚂蚁决战……直到分出胜负。

考虑如何计算概率。注意到每种字符串恰好对应唯一一种将 n 只蚂蚁划分连续段的方案，我们计算能让第 i 只蚂蚁站到最后的连续段方案数 c_i，那么所求概率即为 p_i=\dfrac{c_i}{2^{n-1}}（其中 2^{n-1} 为总的划分方案数）。

第 i 只蚂蚁能站到最后等价于：它吃掉了所有编号小于它的蚂蚁，并且之后一直没有被吃掉。这两部分是互相独立的，可以分开计算。吃掉所有编号小于它的蚂蚁等价于 \lceil\dfrac{i}{2}\rceil\sim i 的蚂蚁全部分到了一起，计算一下可以知道前半段的总方案数为 2^{\lfloor\frac{i}{2}\rfloor}。后半部分可以采用 DP 来计算：设 g_i 表示某蚂蚁在统一 1\sim i 的所有蚂蚁后，接着吃下其他全部蚂蚁的划分方案数，有

用前缀和优化即可做到 O(n) 求解。

#include<cstdio>
#include<algorithm>

using namespace std;

const long long MOD=1e9+7,INV2=(MOD+1)>>1;

int add(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int sub(int x,int y){return x>=y?x-y:x+MOD-y;}

long long fast_pow(long long b,long long p)
{
    long long ans=1;while(p){if(p&1)ans=ans*b%MOD;b=b*b%MOD;p>>=1;}
    return ans;
}
long long INV(long long x){return fast_pow(x,MOD-2);}

long long pw2[2000000],inv2[2000000];
void init(int n)
{
    pw2[0]=inv2[0]=1;
    for(int i=1;i<=n;i++)pw2[i]=pw2[i-1]*2%MOD,inv2[i]=inv2[i-1]*INV2%MOD;
}

long long dp[2000000],sdp[2000000];

int main()
{
    init(1000000);
    int TT=0;scanf("%d",&TT);
    while(TT--)
    {
        int n=0;scanf("%d",&n);
        dp[n]=1;sdp[n]=1,sdp[n+1]=0;
        for(int i=n-1;i>=1;i--)
        {
            int l=i+1,r=min(2*i-1,n);
            dp[i]=sub(sdp[l],sdp[r+1]);
            sdp[i]=add(dp[i],sdp[i+1]);
        }
        for(int i=1;i<=n;i++)
        {
            printf("%lld\n",dp[i]*pw2[i/2]%MOD*inv2[n-1]%MOD);
        }
    }
}