HDU 4828 (卡特兰数+逆)

HDU 4828 Grids

思路:能够转化为卡特兰数,先把前n个人标为0。后n个人标为1。然后去全排列,全排列的数列。假设每一个1的前面相应的0大于等于1,那么就是满足的序列,假设把0看成入栈,1看成出栈。那么就等价于n个元素入栈出栈,求符合条件的出栈序列,这个就是卡特兰数了。

然后去递推一下解,过程中须要求逆元去计算

代码:

#include <stdio.h>
#include <string.h> const int N = 1000005;
const long long MOD = 1000000007; long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
if(a == 0 && b == 0) return -1;
if(b == 0){x = 1; y = 0; return a;}
long long d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
} long long mod_reverse(long long a, long long n)
{
long long x,y;
long long d = extend_gcd(a, n, x, y);
if(d == 1) return (x % n + n) % n;
else return -1;
} int t, n;
long long Catalan[N]; int main() {
Catalan[1] = Catalan[2] = 1;
for (int i = 3; i < N; i++) {
long long tmp = mod_reverse((long long) i, MOD);
Catalan[i] = Catalan[i - 1] * (4 * i - 6) % MOD * tmp % MOD;
}
int cas = 0;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
printf("Case #%d:\n", ++cas);
printf("%lld\n", Catalan[n + 1]); }
return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:Spring(十二)之JDBC框架


下一篇:Spring学习进阶(四) Spring JDBC