HDU-4828 卡特兰数+带模除法

题意：给定2行n列的长方形，然后把1—2*n的数字填进方格内，保证每一行，每一列都是递增序列，求有几种放置方法,对1000000007取余；

思路：本来想用组合数找规律，但是找不出来，搜题解是卡特兰数，而且还有一个难点在于N的范围是1000000，卡特兰数早已数千位，虽然有取余；

解决方法就是用在求卡特兰数的时候快速取余+带模除法；

卡特兰数递归公式1：K(n)=K(n-1) * ((4*n-2)/(n+1)); 组合数公式2：K[n] = C[2*n][n] /(n+1);

看公式1，有个除法运算，K(n-1) * ((4*n-2)很大，无法直接求得K(n-1) * ((4*n-2)/(n+1))的值，因此需要求乘法逆元（满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元，按照倒数理解就好）；

求乘法逆元的方法：扩展欧几里得，费马小定理；

 ///扩展欧几里得

 typedef long long LL ;

 LL exgcd(LL a,LL b,LL &x,LL &y)///使得ax+by==gcd(a,b);

 {

     if( b ==  )

     {

         x = ;

         y = ;

         return a;

     }

     else

     {

         LL x1,y1;

         LL d = exgcd ( b , a % b , x1 , y1 );

         x = y1;

         y= x1 - a / b * y1;

         return d;

     }

 }

扩展GCD

费马小定理说，对于素数 M 任意不是 M 的倍数的 b，都有：

b ^ (M-1) = 1 (mod M)

于是可以拆成：

b * b ^ (M-2) = 1 (mod M)

于是：

a / b = a / b * (b * b ^ (M-2)) = a * (b ^ (M-2)) (mod M)

也就是说我们要求的逆元就是 b ^ (M-2) (mod M)；

 long long C[] = {0LL};

 long long spow(long long x, int n)///递归

 {

     if (n == )

         return x;

     else

     {

         long long v = spow(x, n/);

         if (n% == )

             return v*v%MODLL;

         else

             return v*v%MODLL*x%MODLL;

     }

 }

费马小定理

补充一下卡特兰数的应用（无特别说明答案都是 K（n））：

括号化问题：P=a1*a2*a3*…*an,依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方法。
有n个节点的二叉树共有多少种情形？
一个栈（无穷大）的进栈序列为1,2,3，…,n，有多少个不同的出栈序列？
买票找零问题：球票为50元，有2n个人排除买票，其中n个人手持50元的钞票，n个人持100元的钞票，假设售票处无零钱，问这2n个人有多少种排列方式，不至于使售票处出现找不开钱的局面。
凸多边形的三角剖分问题：求将一个凸多边形区域分成三角形区域的方法数。对于有n条边（n+1个顶点）的多边形的一个三角剖分与具有n-1个叶节点的分析树对应。所以，由n+1个顶点n条边构成多边形的三角剖分数目为h(n-2).
上班路径问题一位律师在住所以北n个街区和以东n个街区工作。每天她走2n个街区去上班。如果她不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
圆上的点连线问题---在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？

巴特西

HDU-4828 卡特兰数+带模除法

最新文章

热门文章