2021“MINIEYE杯”中国大学生算法设计超级联赛（7）Link with EQ

题目描述：n个位置，第一个人随机选，后面的人会选择与其他所有人都最远的位置坐下（如果有多个，则随机选一个），问最多能坐多少人？
思路：考虑n个坐位，第一个人坐在两端任意一个位置时候能坐多少人
设f(x)为 x个位置按先坐两端能坐下多少人，
1.先坐到两端，f(1)=1,f(2)=1
2.然后下一个人必然会坐到(i+1)/2这个位置，问题就转化为f((i+1)/2)与f(i-(i+1)/2+1)能坐多少人，求和再减去(i+1)/2位置重复算的一个。
递推式如下：
$$f(x)=f((i+1)/2)+f(i-(i+1)/2+1)-1$$
然后只需要枚举第一个人做的位置，他的选择可以将作为切成两部分，两部分之间重复算了第一个人选择的那个位置
所以对于n个坐位,可以坐下的人数期望为：
$$ans=\frac{{\sum }_{i=1}^n[f(i)+f(n-i+1)-1]}{n}$$
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+7,mod=1e9+7;
ll f[N],sum[N],inv[N];
ll qmi(ll m, ll k, ll p)
{
    ll res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
int main()
{
	f[0]=0;f[1]=1;f[2]=1;f[3]=2;f[4]=2;
	for(ll i=5;i<=N;i++) f[i]=(f[(i+1)/2]+f[i-(i+1)/2+1]-1)%mod;
	for(ll i=1;i<=N;i++) sum[i]=(sum[i-1]+f[i])%mod;
	for(ll i=1;i<=N;i++) inv[i]=qmi(i,mod-2,mod);
	for(ll i=1;i<=N;i++) sum[i]=2*sum[i]%mod;
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		ll n;
		scanf("%lld",&n);
		ll ans=((sum[n]*inv[n])%mod-1)%mod;
		printf("%lld\n",ans);
	}
}