TC SRM690 DIV2
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------------------
这是令我非常不爽的一把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
--------------------------------------------------------------------------
评论 (0)
