Description
大家的好朋友小 L 来到了博弈的世界。Alice 和 Bob 在玩一个双人游戏。每一轮中，Alice 有 p 的概率胜利，1
-p 的概率失败，不会出现平局。双方初始时各有 0 分，当一个人胜利的时候，他会获得一分，失败则扣掉一分。
遗憾的是，博弈论世界的人目前是无法理解负数的，因此，如果某个人输掉一轮比赛的时候他只有 0 分，那么他
就不会被扣分（对方会照常加一分）。游戏一共要进行 N+M 轮，Alice 想请你帮她算算在游戏结束时她的得分的
数学期望。"这算啥，我小 L 分分钟搞定！"。比小 L 更熟练的你当然也是随手就算出来了，但就在你打算告诉 A
lice 答案之前，博弈论世界之神--temporaryDO 出现了，他给大家带来了一个重要信息：这 N+M 轮游戏中， Ali
ce 恰好赢了 N 轮！熟知条件概率那套理论的你立刻注意到，你需要修改自己的计算方法来得到正确的答案了。为
了避免精度问题，请将结果对 10^9+7 取模。即，我们的数据保证答案是一个有理数 p/q ，且有 10^9+7与q互质
，你只需要找到一个整数 x∈[0,10^9+7) 使得 qx≡p(mod 10^9+7) 即可。
Solution
这题跟 (p) 没关系
设数组 (A) 为得分序列, (B) 为(A) 的前缀和
那么答案就是 (B_n-min(B_i)=n-m-min(B_i)) (不会证明 (QwQ))
现在就是要求 (min(B_i)) 的期望了
把这个过程看成 ((0,0)) 走到 ((n,m)) 的方案数,往右是 (+1),往上是 (-1)
总方案数是 (C(n+m,n))
最小值小于等于 (i) 的方案就是穿过直线 (y=x+i) 的方案
用 (catalan) 数那一套理论,把 ((0,0)) 沿着这条直线对折过去,穿过直线的方案就是这个点到 ((n,m)) 的方案
得分的取值范围是 ([max(n-m,0),n]) ,枚举最小值算一下贡献
假设 (n>=m),容斥一下最小值等于 (i) 的方案
(sum_{i=0}^{m} (C_{n+m}^{n+i}-C_{n+m}^{n+i+1})*(n-m+i))
((n-m)*C_{n+m}^{n}+sum_{i=1}^{m}C_{n+m}^{n+i})
((n-m)*C_{n+m}^{n}+sum_{i=1}^{m}C_{n+m}^{m-i})
((n-m)*C_{n+m}^{n}+sum_{i=0}^{m-1}C_{n+m}^{i})
(n<m) 时
(sum_{i=m-n}^{m} (C_{n+m}^{n+i}-C_{n+m}^{n+i+1})*(n-m+i))
按上面的方法化简出来就是:(sum_{i=0}^{n-1}C_{n+m}^{i})
可以把两种情况的式子总和一下:
(max(0,n-m)*C_{n+m}^{n}+sum_{i=0}^{min(n,m)-1}C_{n+m}^{i})
最后除以 (C_{n+m}^{n}) 就是期望
但是后面一项 (sum_{i=0}^{min(n,m)-1}C_{n+m}^{i}) 不能暴力求
相当于是杨辉三角的一行的前缀和
然后就是一个新套路,莫队维护这个东西
设 (F(n,m)) 表示 (sum_{i=1}^{m}C_{n}^{i})
那么 (F(n,m)->F(n,m+1)) 和 (F(n,m)->F(n+1,m)) 都是可以 (O(1)) 算的
其中 (F(n+1,m)=F(n,m)*2-C_{n}^{m})
(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}) 就可以证明
复杂度有点卡,(bzoj) 过不去
#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
const int N=3e5+10,mod=1e9+7;
int Q,P,B,n=0,Fac[N],inv[N],ans[N],INV[N];
struct data{
int x,y,id,L,R;
inline bool operator <(const data &p)const{
return L!=p.L?L<p.L:R<p.R;
}
}q[N];
inline int C(int a,int b){return 1ll*Fac[a]*inv[b]%mod*inv[a-b]%mod;}
inline int F(int a,int b){return 1ll*Fac[b]*Fac[a-b]%mod*inv[a]%mod;}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
cin>>Q>>P;B=sqrt(Q);
for(int i=1;i<=Q;i++){
gi(q[i].x),gi(q[i].y),q[i].id=i,n=max(n,q[i].y+q[i].x);
q[i].L=(q[i].x+q[i].y)/B;q[i].R=min(q[i].x,q[i].y)-1;
}
Fac[0]=INV[0]=INV[1]=inv[0]=1;
for(int i=2;i<=n;i++)INV[i]=(mod-1ll*(mod/i)*INV[mod%i]%mod)%mod;
for(int i=1;i<=n;i++)Fac[i]=1ll*Fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*INV[i]%mod;
sort(q+1,q+Q+1);
register int l=0,r=0,s=1;
for(int i=1;i<=Q;i++){
int L=q[i].x+q[i].y,R=min(q[i].x,q[i].y)-1;
while(l<L)s=(1ll*(s<<1)-C(l,r)+mod)%mod,l++;
while(l>L)l--,s=1ll*(s+C(l,r))*INV[2]%mod;
while(r<R)r++,s=(s+C(l,r))%mod;
while(r>R)s=(s-C(l,r)+mod)%mod,r--;
ans[q[i].id]=
(max(q[i].x-q[i].y,0)+1ll*s*F(L,q[i].y))%mod;
}
for(int i=1;i<=Q;i++)printf("%d
",ans[i]);
return 0;
}