CF838D Airplane Arrangements

Posted on | Views:

构造 + 概率的计算.

飞机上有 $n$ 个位置,有 $m$ 个乘客入座,每个乘客有一张票 $(x\in [1,n]\cup {\mathbb N_+},dir\in \lbrace 0,1\rbrace)$ .

每个乘客依次进入飞机,先走到位置 $x$ ,若 $dir =0$ ,则向前走,直到找到一个空位并坐下.

若 $dir = 1$ ,则向后走,直到找到一个空位并坐下.

若每个乘客都能找到一个空位,则是合法的情况,问有多少种情况是合法的,答案对 $10^9+7$ 取模.

$1\le m\le n\le 10^6​$ ,两种情况不同当且仅当存在一个乘客,他在两种情况中拥有的票不一样.

考虑新加入一个特殊位置 $n+1$ ,若有乘客走到这里坐下,说明不合法.

然后就可以将序列变成一个环.每个乘客在环上选一个位置和一个方向出发,直到找到空位并坐下.

可以发现如果我们允许乘客从 $n+1​$ 出发,合法方案数也不会变,但可以使得每个位置都等价.

乘客共选了 $m$ 个位置, 位置 $n+1$ 没有被选的概率为 $\frac{n+1-m}{n+1}$ ,再乘上总方案数 $(2n+2)^m$ 即为合法方案数.

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int P = 1e9 + 7;
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
int main()
{
	int n = read(), m = read();
	printf("%d\n", mul(n + 1 - m, mul(fpow(n + 1, P - 2), fpow(2 * n + 2, m))));
	return 0;
}