hdu4828（卡特兰数+逆元）

本文主要是介绍hdu4828（卡特兰数+逆元），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题的前几个数据分别为1,2,5,14,32......................然后确定这是个卡特兰数列

下面来介绍下卡特兰数,它的递推式为f[i+1] = f[i]*(4*n - 6)/n，其中f[2] = f[3] =1;f[4] = 2;f[5] = 14;f[6] = 32..................................

但是这题的n太大了，所以要用到逆元，这里除以一个数，就相当于乘以一个数的逆元。

代码如下（附注释）：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define ll long long
#define N 1000010
#define MOD 1000000007
#define inf 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
ll f[N];void exgcd(ll a,ll b,ll& d, ll &x, ll &y)//扩展欧几里得算法，模板
{if(!b) {d = a; x = 1; y = 0;}else{exgcd(b,a%b,d,y,x);y -= x*(a/b);}
}ll inv(ll a, ll n)//求a模n的逆元，也是模板
{ll d, x, y;exgcd(a,n,d, x, y);return d == 1 ? (x+n)%n : -1;
}int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);ios::sync_with_stdio(false);ll i;f[3] = 1;//f[4] = 2;for(i = 3; i < N-5; i++){f[i+1] = (4*i-6)%MOD;f[i+1] = f[i+1]*f[i]%MOD;ll k = inv(i,MOD);f[i+1] = (f[i+1]*k)%MOD;}ll t, z = 1;cin>>t;while(t--){ll n;cin>>n;printf("Case #%d:\n",z++);cout<<f[n+2]<<endl;}return 0;
}

这篇关于hdu4828（卡特兰数+逆元）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---