记录编号	413827	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的卡特兰数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.294 s
提交时间	2017-06-12 18:16:06	内存使用	8.29 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1<<20|1,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
//dp[i][j]表示在i边形中取j条边的方案数
//dp[i][0]=1
//dp[i][j]=dp[i][j-1]*(i+j-1)*(i-j-2)/j/(j+1)
int n,inv[N],dp[N],ans;
int calc(int n){
	int ans=1;
	dp[0]=1;
	for (int i=1;i<=n;i++){
		dp[i]=mul(dp[i-1],mul(n+i-1,mul(n-i-2,mul(inv[i],inv[i+1]))));
		ans=inc(ans,dp[i]);
	}
	return ans;
}
int main()
{
	freopen("Crazy_Catalan.in","r",stdin);
	freopen("Crazy_Catalan.out","w",stdout);
	scanf("%d",&n);
	inv[1]=1;
	for (int i=2;i<=n+1;i++) inv[i]=mul(p-p/i,inv[p%i]);
	dp[0]=ans=1;
	for (int i=1;i<=n;i++){
		dp[i]=mul(dp[i-1],mul(n+i-1,mul(n-i-2,mul(inv[i],inv[i+1]))));
		ans=inc(ans,dp[i]);
	}
	printf("%d\n",ans);
	return 0;
}