链接
https://acm.hdu.edu.cn/showproblem.php?pid=7048
题意
有连续的 n 个空座位，按如下规则入座：
- 当全空时，随机选一个座位入座；
- 当无论坐哪里都会挨着人时，无法入座；
- 否则选择能使离其余已经有人的座位的距离的最小值最大的座位入座，如果有多个，随机选一个。
求期望入座人数。
思路
要使离其余已经有人的座位的距离的最小值最大，那么一定会选择边界位置或者连续空座位的中间位置入座。
记 $f_i$ 为长度为 $i$ 的连续空座位且左端点的左侧右端点的右侧都有人的情况能坐下的期望人数：
$$f_i=\begin{cases}
0 & i\le 2\
2f_{\lfloor\frac{i+1}{2}\rfloor-1}+1 & i%2=1\
f_{\frac{i}{2}-1}+f_{\frac{i}{2}}+1 & i%2=0
\end{cases}$$
记 $f_i$ 为长度为 $i$ 的连续空座位一端靠着人一端靠着边界的情况能坐下的期望人数：
$$g_i=\begin{cases}
0 & i\le 1\
f_{i-1}+1 & i>1
\end{cases}$$
记 $h_i$ 为长度为 $i$ 的连续空座位两端都靠着边界的情况能坐下的期望人数：
$$h_i=\frac{1}{i}\sum_{j=1}^i{g_{j-1}+g_{i-j}+1}=1+\frac{2}{i}\sum_{j=0}^{i-1}{g_j}$$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL MOD=1e9+7;
const int N=1e6+5;
LL f[N],g[N],h[N];
LL qpow(LL a,LL b) {
LL ret=1;
while(b) {
if(b&1) ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i=3;i<=1000000;i++) {
if(i&1) f[i]=(f[(i-1)/2]*2+1)%MOD;
else f[i]=(f[i/2-1]+f[i/2]+1)%MOD;
}
for(int i=2;i<=1000000;i++) g[i]=(f[i-1]+1)%MOD;
for(int i=2;i<=1000000;i++) g[i]=(g[i]+g[i-1])%MOD;
for(int i=1;i<=1000000;i++) h[i]=(g[i-1]*2+i)%MOD*qpow(i,MOD-2)%MOD;
int T;cin>>T;
while(T--) {
int n;cin>>n;
cout<<h[n]<<'\n';
}
return 0;
}
|