分类 题解 下的文章
UOJ496 新年的新航线
CF590E
AGC022F - Checkers
AGC021E - Ball Eat Chameleons
题意
有$n$个变色龙，初始都为蓝色，没吃过任何球。每次可以投入一个红球或一个蓝球，然后会有一只变色龙吃掉它。如果一只变色龙吃掉的红球比蓝球多，就会变为红色，如果蓝球比红球多，就会变为蓝色，如果一样多就不会变。
求有多少个长度为$k$的投球序列满足存在一种吃法使得最后每个变色龙都是红色。
$n,k\le 5\cdot 10^5$
<!--- more -->
题解
枚举投入的红球数$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)$。