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

时间:2021-08-20 08:53:02

题意:给定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)):

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