2019年11月

link

题意

有$n$个变色龙,初始都为蓝色,没吃过任何球。每次可以投入一个红球或一个蓝球,然后会有一只变色龙吃掉它。如果一只变色龙吃掉的红球比蓝球多,就会变为红色,如果蓝球比红球多,就会变为蓝色,如果一样多就不会变。

求有多少个长度为$k$的投球序列满足存在一种吃法使得最后每个变色龙都是红色。

$n,k\le 5\cdot 10^5$

题解

枚举投入的红球数$r$,蓝球数$b$,使得$r+b=k$。

如果$r<b$则显然不可能。

如果$r=b$则要求最后一个球是蓝球,且存在一种找出$n$对红球-蓝球的配对关系使得红球在蓝球左边,且每个球最多被选一次。

如果$r>b$则至少有$r-b$个变色龙不用考虑顺序,只需要找出$max(n-(r-b),0)$个一样的配对关系即可。

定义$f(r,b,n)$表示$r$个红球,$b$个蓝球,要找出$n$个配对关系的方案,那么$r=b$方案就是$f(r,b-1,n-1)$,$r>b$就是$f(r,b,max(n-(r-b),0))$。

考虑$f(r,b,n)$的求法。

发现如果可以选出配对关系,一定存在一种方案红球是前$n$个红球,蓝球是后$n$个蓝球。那么就是说第$b-n+1$个蓝球前一定有一个红球,$b-n+2$个蓝球前一定有2个红球$\dots$。

如果把选球的过程相当于从$(0,0)$每次可以$x+1$或$y+1$,要求走到$(r,b)$的方案数,那么一定不能经过$y=x+(b-n+1)$上方的部分。

对于经过了的情况,我们把第一次到达之后的$x+1$都变成$y+1$,$y+1$变成$x+1$,也就是关于这条直线对称,那么最后走到的点就是$(r,b)$关于这条直线对称的点。

两个组合数算一下就可以了。

时间复杂度$O(n+k)$。