马特维尔兔窟

公式都化出来的,居然还要对着数据调了半天....囧

题意大概是:给你一个n*m的棋盘和k种颜色,求满足要求的涂色方案,额...要求就是:垂直方向把棋盘分成两边(非空),不管怎么分,两边的颜色种数相等....

满足要求的方案首先要最左最右的满足颜色数相等,然后中间,在最左和最右边的交集中随意取;

最后化出来就是:

t1=min(m,k),t2=min(m-i,(k-i)/2);

这个F(x)表示x种颜色填到n个格子里,每种至少一个,有多少种涂法:

F(1)=1,F(x)=x^n-F(x-1)-F(x-2)-...-F(1);

核武的思路:http://hi.baidu.com/aekdycoin/blog/item/69e075f5e200bcf47709d769.html

参考完核武报告,没完全懂~翻了翻组合数学书,这实质上就是求元素可重复的圆排列--许多组合数学书里讲莫比乌斯反演时唯一的例题~

先求 r 种不同元素,放在圆的n个点上 , 有几种放法, 旋转后相同算一种.

做法是:设周期为为d,d|n,的方案数是Td(r) 则 每个这样的圆排列,对应着d个线排列

线排列总数是r^n,所以:

莫比乌斯反演后:

总的方案数M_n就是各种周期的和:

因  d|k|n  , 设k'=k/d . n'=n/d

注意到后面一部分和等于n'的欧拉函数,故Mn可以写成:

问题基本解决,剩下就是核武报告里说差不多,把最小公约数是i的倍数的方法数求出,容斥原理搞搞.

最后的答案应该是:

其中r_n表示重量是n的倍数的石子种数

mu(n)  和 phi(n) 都可以在预处理时筛出来,

n的分解只需要搞一遍就够了~

遗憾的是,还是很慢,board的第一名时空复杂度都比我写的好~ym

http://en.wikipedia.org/wiki/Catalan_number

catalan数的身世,wiki(上面链接)有....那里还提供了5种(?)求法~第一种:母函数,第二种:全体数-非法数,第三种:通过定义一个叫exceedance的玩意,然后通过一个很奇葩的构造,说明exceedance等于0,1,2...n的路径数相等,直接得出结果~第四种是基于卡特兰数在多边形的三角划分的,推出个递推式~第五种是根据递推式,死推~

昨天,上海网赛热身,那题http://acm.hdu.edu.cn/showproblem.php?pid=4015,  是一个很像很像catalan数的玩意~大概是:给你两种数,a,b,权值分别是1和-m , a有k*m+1个,m有k个 , 问有几种排列方法,使得前任意项的和都不为0;

m取1时,就是红果果的catalan数~

m!=1时 ~ 不会..不过又找到了卡特兰数一个牛B的不同于wiki那5种的求法,完全兼容上面那题~这是本文存在的原因~

原文在这里,里面还有好几种别的求法:谷歌文档~偷来了,怕丟不好意思

现在 说说那个求法:

给你n+1个'/'和n个'\'  ,  让你用这些随意的首尾相接组到一起, 一共就C(2n+1,n)种组法,我们要求的是除起点外所有点的海拔都大于0的组合数;

每种(含非法)组法就称为一个pattern , 显然这些pattern有一个性质,最后那点比第一点高出一个单位;

还有一个不那么显然的性质:在连接最后一点和第一点的直线上,没有一个\或/的端点落在上面,这是因为最后那点才是1,落在上面就意味着有分数,这不可能;

高潮来了~现在把两个相同的pattern首位相接,从前面不同的2n+1位开始的2n+1位,一共有2n+1个不同(why?我再想想)的pattern:其中,只有一个是合法的!!!(想象一条斜率为1/(2n+1)的直线从底部缓缓升起)

so~总的合法序列就C(2n+1,n)/(2n+1)个~

用这个来做上面的那道题,没压力啊,连化简都省了,直接出结果啊!~~~