[Code+#3]博弈论与概率统计

记得曾经和稳稳比谁后抄这个题的题解，看来是我输了

不难发现\(p\)是给着玩的，只需要求一个总情况数除以\(\binom{n+m}{n}\)就好了

记\(i\)为无效的失败次数，即\(\rm Alice\)在得分为\(0\)时的失败次数，那么最后的得分就是\(n-m+i\)

不妨将赢看成\(1\)输看成\(-1\)，我们把输赢情况写成一个\(n+m\)的序列，记这个序列的最小前缀和为\(t\)，那么无效失败次数就是\(|\min(0,t)|\)，也就是当\(t<0\)的时候，得分应为\(n-m+|t|\)

证明的话，考虑一种构造方法，我们把对最小前缀和产生影响的\(t\)个\(-1\)拿出来，显然两个\(-1\)之间的数的和应为\(0\)，和为\(0\)意思就是分数可能涨了涨但最后又扣成\(0\)了，于是在得分为\(0\)的时候失败的次数就是\(t\)次

之后套路的转化成一个平面上的问题，将\(-1\)视为向上走，\(1\)视为向右走，那么无效失败次数为\(i\)的方案数等价与在坐标系上从\((0,0)\)走到\((n,m)\)且经过至少一次\(y=x+i\)且不超过的方案数

简单容斥一下，求一下严格低于\(y=x+i+1\)的方案数减一下严格低于\(y=x+i\)的方案数就好了

这个老哥的博客里的图挺好的

对于一个不合法的方案，我们取第一次达到\(y=x+i\)之前的路径，并将这段路径沿\(y=x+i\)翻折，就得到了一条从\((-i,i)\)到\((n,m)\)的路径，不难发现这样的路径会经过至少一次\(y=x+i\)，所以这样的路径和不合法的路径是一一对应的，显然这样的路径条数是\(\binom{n+m}{n+i}\)

于是严格低于\(y=x+i\)的路径条数就是\(\binom{n+m}{n}-\binom{n+m}{n+i}\)，于是恰好经过经过至少一次\(y=x+i\)且不超过的方案数为\(\binom{n+m}{m}-\binom{n+m}{n+i+1}-\binom{n+m}{n}+\binom{n+m}{n+i}=\binom{n+m}{n+i}-\binom{n+m}{n+i+1}\)

对于\(n\geq m\)的情况，我们求得即为\(\sum_{i=0}^m(n-m+i)(\binom{n+m}{n+i}-\binom{n+m}{n+i+1})\)

简单划开就会发现求得其实是\((n-m)\binom{n+m}{m}+\sum_{i=0}^{m-1}\binom{n+m}{n+i}\)

多组询问求后面那个柿子好像还是一道题来着，直接大力莫队即可

巴特西

[Code+#3]博弈论与概率统计

最新文章

热门文章