TC SRM690 DIV2

--------------------------------------------------------------------------
这是令我非常不爽的一把TC
某CZH和我一起做,明明比我低了几百分
最后涨的rating居然比我多
这就算了
涨完后他的总rating居然也比我高(我本来就比他高)
这是什么鬼算分机制啊
 
--------------------------------------------------------------------------
250 500 SB题就不说了,这里说一下1000的O(n)做法(原题是n<=1000,但是毕竟是Div2嘛,其实这个题是可以O(n)做的)
题意相当于是让你把0~2n-1的数填入2行n列的矩阵
要求每一行的最大值都必须大于等于k
并且定义一个填法的“生成序列”A,Ai是第i列的最大值,An+p是第p行最大值
问有多少个合法的生成序列
 
先不妨假设第一行的最大值大于第二行的最大值,最后答案乘以2就行了
枚举一下第二行最大值,假设为q
那么q+1~2*n-1坑定都在第一行
先把这(2*n-1-q)个数放好,方案数为C(n,2*n-1-q)*(2*n-1-q)!
然后考虑放剩下的格子,还剩q+1个格子,还剩(q+1-n)个最大值,剩下的数就没有上下之分了
想像一下剩下所有数从小到大排成一排,要从中选(q+1-n)个人当较大值
显然选法数再全排列一下就是剩下格子的填法数
一个选法是合法的条件是什么呢?
任意前i个数,选来做最大值的人数大于等于剩下的人数
这就是Catalan number那一套理论啦
不妨设f(x,y)是从x个数中选y个数来做较大值的方案数
显然有f(x,y)=C(x,y)-C(x,y-1)
所以最大值q对答案的贡献就是C(n,2*n-1-q)*((2*n-1-q)!)*(C(q+1,q+1-n)-C(q+1,q-n))*((q+1-n)!)
然后就做完啦,最后答案不要忘了乘以2
--------------------------------------------------------------------------