Code+三月月赛 Div1 C 博弈论与与概率统计（莫队+组合数+数学期望）

发表于 |
字数统计: 1,404字 | 阅读时长 ≈ 7min

[CODE+]博弈论与概率统计

问题描述

这里写图片描述

样例输入

3 500
1 1
2 3
4 4

样例输出

500000004
200000002
728571435

提示

这里写图片描述

首先，容易得到题目中的p是没有用的，因为Alice每一种输赢序列的出现概率是相等的，因此只需要算出每种排列的得分之和再除以$C_{n+m}^{n}$即可。

然后将赢记作1，输记作-1，那么得到一个序列$a_i$，对其求前缀和得到$b_i$
观察可以发现，最终得分等于$\sum a_i-min(b_i)$，即$n-m-min(b_i)$
那么最终答案等于$(n-m)C_{n+m}^{n}-\sum min(b_i)$

考虑求后面的东西，令$F[k]$表示$b_i$的最小值恰为$k$的排列数，令$G[k]$表示$b_i$的最小值小于等于$k$的排列数
考虑利用折线法来求得$G[k]$

注意到最终的$b_{n+m}$一定是$n-m$，那么我们可以认为$a_i=1$表示从$(x,y)$走到$(x+1,y+1)$，而$a_i=-1$表示从$(x,y)$走到$(x+1,y-1)$，那么$a_i$序列就是从$(0,0)$走到$(n+m,n-m)$的一条折线。

考虑$b_i$的最小值小于等于$k$的意义，不妨令恰好取得最小值时，前面有$x$个$1$，$y$个$-1$，那么有$x-y<=k$，反映到折线上就是这条折线至少有一个点的纵坐标小于等于$k$，也就是折线与$y=k$有交。

不妨将折线与$y=k$第一次相交后的部分沿$y=k$对称，对称前后的折线一一对应，那么对称后的折线终点是$(n+m,2k-n+m)$，那么此时对应的$a_i$中有$k+m$个1，$n-k$个-1，且这样的折线有$C_{n+m}^{m+k}$条，对应的$a_i$序列也就有这么多个。

因此我们得到$G[k]=C_{n+m}^{m+k}$，进一步的$F[k]=G[k]-G[k-1]=C_{n+m}^{m+k}-C_{n+m}^{m+k-1}$

为了得到答案，我们考虑$min(b_i)$的取值范围
容易得到$n>=m时，min(b_i)\in[-m,0]$，当$n<m时，min(b_i)\in[-m,n-m]$，因此需要分类讨论

先考虑$n>=m$时，得到$Ans=(n-m)C_{n+m}^{n}-\sum_{k=-m}^{0}k(C_{n+m}^{m+k}-C_{n+m}^{m+k-1})$，推导一番
$$
Ans=(n-m)C_{n+m}^{n}+\sum_{k=0}^{m}k(C_{n+m}^{m-k}-C_{n+m}^{m-k-1})=(n-m)C_{n+m}^{n}+\sum_{k=0}^{m}kC_{n+m}^{m-k}-\sum_{k=0}^{m-1}kC_{n+m}^{m-1-k}
$$

$$
Ans=(n-m)C_{n+m}^{n}+\sum_{k=0}^{m-1}C_{n+m}^{m-1-k}=(n-m)C_{n+m}^{n}+\sum_{k=0}^{m-1}C_{n+m}^{k}
$$

我们发现是一个组合数前缀和的形式，不妨再看看$n<m$时的情况。类似的处理
$$
Ans=(n-m)C_{n+m}^{n}-\sum_{k=-m}^{n-m}k(C_{n+m}^{m+k}-C_{n+m}^{m+k-1})=(n-m)C_{n+m}^{m}+\sum_{k=m-n}^{m}kC_{n+m}^{m-k}-\sum_{k=m-n}^{m-1}kC_{m+n}^{m-1-k}
$$

$$
Ans=(n-m)C_{n+m}^{n}+(m-n)C_{n+m}^{n}+\sum_{k=m-n}^{m-1}C_{n+m}^{m-1-k}=\sum_{k=0}^{n-1}C_{n+m}^{k}
$$

我们发现同样是一个组合数前缀和的形式，那么接下来考虑如何求组合数前缀和。注意到
$$
\sum_{k=0}^{m}C_{n+1}^{k}=\sum_{k=0}^{m}(C_{n}^{k}+C_{n}^{k-1})=2\sum_{k=0}^{m}C_{n}^{k}-C_{n}^{m}
$$
因此，如果我们已知$\sum_{k=0}^{m}C_{n}^{k}$，可以$O(1)$得到$\sum_{k=0}^{m}C_{n+1}^{k}$，反之亦然

因此我们可以用莫队算法来处理多次询问。总时间复杂度$O((N+M)\sqrt{N+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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 250005
using namespace std;
const int mod=1e9+7,inv2=1000000008>>1;
int id[N],T,p,fac[N],inv[N],Ans;
struct node{int id,l,r;}K[N],A[N];
bool operator<(node a,node b)
{
	if(id[a.l]==id[b.l])return a.r<b.r;
	return id[a.l]<id[b.l];
}
void add(int &x,int y){x+=y;x-=x>=mod?mod:0;}
void sub(int &x,int y){x-=y;x+=x<0?mod:0;}
int mul(int x,int y){return 1ll*x*y%mod;}
int C(int n,int m)
{
	if(n<m)return 0;
	return mul(fac[n],mul(inv[m],inv[n-m]));
}
int inv_C(int n,int m)
{
	return mul(inv[n],mul(fac[m],fac[n-m]));
}
void UD1(int n,int m)
{
	Ans=mul(Ans,2);
	sub(Ans,C(n,m));
}
void UD2(int n,int m)
{
	add(Ans,C(n-1,m));
	Ans=mul(Ans,inv2);
}
void UD3(int n,int m)
{
	add(Ans,C(n,m+1));
}
void UD4(int n,int m)
{
	sub(Ans,C(n,m));
}
void Solve()
{
	int i,j,k,n,m,S=477;
	for(i=1;i<N;i++)id[i]=i/S;
	sort(K+1,K+T+1);
	n=0;m=0;Ans=1;
	for(i=1;i<=T;i++)
	{
		while(n<K[i].l)UD1(n++,m);
		while(n>K[i].l)UD2(n--,m);
		while(m<K[i].r)UD3(n,m++);
		while(m>K[i].r)UD4(n,m--);
		add(A[K[i].id].id,Ans);
	}
}
int main()
{
	int i,j,k,n,m;
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(i=2;i<N;i++)
	{
		fac[i]=mul(fac[i-1],i);
		inv[i]=mul(inv[mod%i],mod-mod/i);
	}
	for(i=2;i<N;i++)inv[i]=mul(inv[i],inv[i-1]);
	scanf("%d%d",&T,&p);
	for(i=1;i<=T;i++)
	{
		scanf("%d%d",&n,&m);
		A[i].l=n;A[i].r=m;
		if(n>=m)A[i].id=mul(n-m,C(n+m,n)),K[i]=(node){i,n+m,m-1};
		else K[i]=(node){i,n+m,n-1};
	}
	Solve();
	for(i=1;i<=T;i++)
	{
		A[i].id=mul(A[i].id,inv_C(A[i].l+A[i].r,A[i].l));
		printf("%d\n",A[i].id);
	}
}