题目链接：点击打开链接
题目大意：略。
解题思路：卡特兰数 点击打开链接 + 乘法逆元 点击打开链接。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int mod=1000000007; ll h[10000000]; // 快速模幂（配合：费马小定理） ll qpow(ll a,ll b) { ll ans=1; a=a%mod; while(b) { if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans; } int main() { //h(n)=h(n-1)*(4*n-2)/(n+1); h[0]=h[1]=1; for(int i=2;i<1000100;i++) { h[i]=h[i-1]*(4*i-2)%mod*qpow(i+1,mod-2)%mod; } ll n; while(~scanf("%lld",&n)) { printf("%lld\n",h[n]); } return 0; }
