CF1737E Ela Goes Hiking

题目大意

nnn 只蚂蚁站成一排，第 111 只蚂蚁左边和第 nnn只蚂蚁右边各有一个挡板，相邻两只蚂蚁的距离、第 111 只蚂蚁与左边挡板的距离和第 nnn 只蚂蚁与右侧挡板的距离相等。初始时每只蚂蚁重量相等，每只蚂蚁有 12\frac{1}{2}21​ 概率向左运动，12\frac{1}{2}21​ 概率向右运动，每只蚂蚁速度相同。中途蚂蚁不可主动改变方向，如果碰到挡板则向相反方向运动，若两只蚂蚁相遇，重量大的蚂蚁会把重量小的蚂蚁吃掉，重量变为两者之和，如果重量相同，向左运动的蚂蚁会吃掉向右运动的蚂蚁。求对于所有 1≤i≤n1\leq i\leq n1≤i≤n，第 iii 只蚂蚁成为最终的存活者的概率对 109+710^9+7109+7 取模。

题解

我们可以发现，每只初始向左的蚂蚁一定会吃掉它左边连续的向右边的蚂蚁。对于最右边的蚂蚁，它无论向那个方向，都会转到向左，我们可以认为它一定向左。

把所有初始向左的蚂蚁吃完后，现在还剩几只大蚂蚁。第一只先跟第二只决斗，然后胜者跟第三只决斗，以此类推。两只蚂蚁决斗，如果重量不同，则重量大的蚂蚁获胜，否则在右边的蚂蚁获胜。

第iii只蚂蚁要获胜，首先它要向右吃掉所有编号比它小的蚂蚁。然后与编号比它大的蚂蚁决斗时，必须是它胜利。我们分成两步来做。

首先，它要吃掉所有编号小于它的蚂蚁。设iii之前第一只向左走的蚂蚁为jjj，则无论111到jjj中哪只蚂蚁获胜，都会变成一只体重为jjj的蚂蚁，而此时iii的重量为j−ij-ij−i，也就是要满足j≤i−jj\leq i-jj≤i−j，即j≤⌊i2⌋j\leq \lfloor\dfrac{i}{2}\rfloorj≤⌊2i​⌋。那么编号为111到⌊i2⌋\lfloor\dfrac{i}{2}\rfloor⌊2i​⌋的蚂蚁可以任意选，而编号为⌊i2⌋\lfloor\dfrac{i}{2}\rfloor⌊2i​⌋到i−1i-1i−1的蚂蚁必须向右走，并被蚂蚁iii吃掉。那么左边的方案数为2⌊i2⌋2^{\lfloor\frac i2\rfloor}2⌊2i​⌋。

然后考虑右边的情况。设iii之后第一个只向右走的蚂蚁为jjj，则显然要满足i

fi=∑j=i+12i−1fjf_i=\sum\limits_{j=i+1}^{2i-1}f_jfi​=j=i+1∑2i−1​fj​

可以用前缀和优化DP。

那么位置iii的蚂蚁最终能获胜的概率为2⌊i2⌋×fi2n−1\dfrac{2^{\lfloor\frac i2\rfloor}\times f_i}{2^{n-1}}2n−12⌊2i​⌋×fi​​（因为第nnn只蚂蚁一定向左，所以不用考虑它，总方案数为2n−12^{n-1}2n−1）。

时间复杂度为O(∑n)O(\sum n)O(∑n)。

code

#include
using namespace std;
const int N=1000000;
int T,n;
long long ans,ny2=500000004,w[1000005],ny[1000005],f[1000005],s[1000005];
long long mod=1000000007;
int main()
{w[0]=ny[0]=1;for(int i=1;i<=N;i++){w[i]=w[i-1]*2%mod;ny[i]=ny[i-1]*ny2%mod;}scanf("%d",&T);while(T--){scanf("%d",&n);f[n]=s[n]=1;s[n+1]=0;for(int i=n-1;i>=1;i--){f[i]=(s[i+1]-s[min(2*i,n+1)]+mod)%mod;s[i]=(s[i+1]+f[i])%mod;}for(int i=1;i<=n;i++){ans=w[i/2]*f[i]%mod*ny[n-1]%mod;printf("%lld\n",ans);}}return 0;
}