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

https://acm.hdu.edu.cn/showproblem.php?pid=7048

题意：

一张可以做n个人的桌子，第一个人随便找一个位置坐，后面的人找一个距离有人的最短距离最大的位置坐。

当一个人发现他必须要和某个人挨着坐时，这张桌子就满了。

问当桌子坐满的时候，期望做了多少个人

这是个线形的桌子，一直以为是圆桌。。。

第一个人位置确定后，这个桌子能坐多少人也定好了

设f[i]表示有连续的i+2个位置，两头都被坐了，还剩下中间i个空位，还能够坐的人数

g[i]表示有连续的i+1个位置，一头被坐了，还剩下i个空位，还能够坐的人数

h[i]表示有连续的i个位置能够坐的人数

f[i]：

若i是奇数，那么下一个人会坐最中间

若i是偶数，那么下一个人会坐中间2个中的某一个。无论坐哪个，分成的左右两部分是一样的

所以可以认为下一个人坐下之后，会把i分为 (i-1)/2 和 i-1-(i-1)/2 两部分

所以 f[i]=f [(i-1)/2]+f[i-1-(i-1)/2]+1，i>=3

当i<3时，f[i]=0

g[i]：

一头被坐了，下一个人必须坐距离它最远的位置，所以会坐到另一头

所以g[i]=f[i-1]+1，i>=2

当i<2时，g[i]=0

h[i]：

枚举第一个人坐在哪儿，设为x

这样他把桌子分为左右两边，两边都是坐了一头

h[i]=( ∑ g[x-1]+g[i-x]+1 ) / i ，x∈[1,i]

h[i]= 2*(∑ g[x] ) / i ，x ∈[0,i-1]

#include<bits/stdc++.h>

using namespace std;

#define N 1000001

const int mod=1e9+7;

int f[N],g[N],sg[N],inv[N];

int main()
{
    for(int i=3;i<N;++i) f[i]=(f[i-1>>1]+f[i-1-(i-1>>1)]+1)%mod;
    for(int i=2;i<N;++i) g[i]=f[i-1]+1;
    for(int i=2;i<N;++i) sg[i]=(sg[i-1]+g[i])%mod;
    inv[1]=1;
    for(int i=2;i<N;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    int T,n,ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        ans=(2ll*inv[n]*sg[n-1]%mod+1)%mod;
        printf("%d
",ans);
    }
}