题意：

A和B玩游戏，每轮A赢的概率为p。现在有T组询问，已知A赢了n轮输了m轮，没有平局，赢一局A得分+1，输一局得分-1，问A得分期望值？

$n+m,T\leq 2.5\times 10^5.$

 

题解：

首先p并没有用。我们需要的是计算所有可能局面A的得分和，最后除以$C_{n+m}^{n}$。

发现得分不小于0非常奇怪，转化一下，考虑设最后一个为0的状态：A赢x次，输y次。那么得分为(n-x)-(m-y)=n-m+y-x。令k=y-x，则y=k+x。其中需要满足$k\geq \max(m-n,0)$，原因：既要保证之前得分$\leq 0$（$y\geq x$），又要保证之后不会出现$\leq 0$（$m-y\leq n-x$）。

(x,y)抽象成平面上的点。整个游戏相当于一条从(0,0)到(n,m)的路径，A赢横坐标+1，A输纵坐标+1，它的得分应该是路径上y-x最大的点的y-x+n-m（最后一个0的状态肯定是在那里取到）。

直接统计得分不那么容易。考虑对于某一个k计算经过直线y=x+k的路径条数$S_k$，那么它们的分数肯定$\geq k+n-m$。$S_k-S_{k-1}$就是分数恰好为k+n-m的路径条数。如何计算$S_k$？将(0,0)到路径和y=x+k的第一个交点这部分沿y=x+k翻转，那么等价于计算(-k,k)到(n,m)的路径条数，方案数为$C_{n+m}^{n+k}$。

假设$n\ge m$，那么可以列出这样一个式子：

$$\begin{equation}ans=\sum_{k=0}^{m}(C_{n+m}^{n+k}-C_{n+m}^{n+k+1})(n-m+k)\end{equation}$$

一看就可以列项，化简以后得：

$$\begin{equation}ans=(n-m)C_{n+m}^{n}+\sum_{k=0}^{m-1}C_{n+m}^{k}\end{equation}$$

$n\leq m$同理，此时k从m-n开始，化简以后得：

$$\begin{equation}ans=\sum_{k=0}^{n-1}C_{n+m}^k\end{equation}$$

于是我们只需处理$\sum_{k=0}^{n}C_n^k$。设为$F(n,k)$，注意到$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$，所以$F(n+1,k)=2F(n,k)-C_n^k$；同时$F(n,k+1)=F(n,k)+C_n^{k+1}$。

发现每次n±1/k±1的时候都可以快速维护F(n,k)，可以莫队维护（或者分块预处理组合数）。

并不是一定要长得像区间的东西才能用莫队维护。二维的且每次行列变化1后的结果能快速得到的量，也可以抽象成莫队问题。（听说莫队常数比分块来得小）

复杂度$\mathcal{O}(n\sqrt{n})$。（理解了我半天）

 

code:

（bzoj卡常并不能过）

1 #include
      
        2 #define rep(i,x,y) for (int i=(x);i<=(y);i++) 3 #define per(i,x,y) for (int i=(x);i>=(y);i--) 4 #define ll long long 5 #define inf 1000000001 6 #define y1 y1___ 7 using namespace std; 8 char gc(){ 9     static char buf[100000],*p1=buf,*p2=buf;10     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;11 }12 //#define gc getchar13 ll read(){14     char ch=gc();ll x=0;int op=1;15     for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-1;16     for (;isdigit(ch);ch=gc()) x=(x<<1)+(x<<3)+ch-'0';17     return x*op;18 }19 #define N 25000520 #define mod 100000000721 #define inv2 50000000422 int Q,fac[N],inv[N],ans[N];23 struct ask{
    int n,m,l,r,id,bl;}q[N];24 int ksm(int x,int p){25     int ret=1;26     for (;p;p>>=1,x=(ll)x*x%mod) if (p&1) ret=(ll)ret*x%mod;27     return ret;28 }29 void init(int n){30     fac[0]=1;31     rep (i,1,n) fac[i]=(ll)fac[i-1]*i%mod;32     inv[n]=ksm(fac[n],mod-2);33     per (i,n-1,0) inv[i]=(ll)inv[i+1]*(i+1)%mod;34 }35 bool cmp(ask x,ask y){
    return x.bl
       
        
         =m?(ll)fac[n]*inv[m]%mod*inv[(n)-(m)]%mod:0)37 #define invC(n,m) ((ll)fac[m]*fac[(n)-(m)]%mod*inv[n]%mod)38 void upd(ll &x,int y){x+=y;x-=x>=mod?mod:0;}39 int main(){40     init(250000);41     Q=read();read();int blo=sqrt(Q);42     rep (i,1,Q){43         q[i].n=read(),q[i].m=read();44         q[i].id=i;45         q[i].l=q[i].n+q[i].m;q[i].r=min(q[i].n,q[i].m)-1;46         q[i].bl=(q[i].l-1)/blo+1;47     }48     sort(&q[1],&q[Q+1],cmp);49     int l=0,r=0;ll now=1;50     rep (i,1,Q){51         while (l>q[i].l) l--,upd(now,C(l,r)),now=(ll)now*inv2%mod;52         while (r
         
          q[i].r) upd(now,mod-C(l,r)),r--;55         ans[q[i].id]=(max(q[i].n-q[i].m,0)+now*invC(q[i].l,q[i].n))%mod;56     }57     rep (i,1,Q) printf("%d\n",ans[i]);58     return 0;59 }