P1641 [SCOI2010]生成字符串

卡特兰数板子。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005
const int p = 20100403;
int n, m, fac[N], inv[N];
int qpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1)
		{
			ans = (ans * x) % p;
		}
		x = (x * x) % p;
		y >>= 1;
	}
	return ans;
}
void init()
{
	fac[1] = 1;
	for(int i = 2; i < N; i++)
	{
		fac[i] = fac[i - 1] * i;
		fac[i] %= p;
	}
	inv[N - 1] = qpow(fac[N - 1], p - 2);
	for(int i = N - 2; i >= 1; i--)
	{
		inv[i] = (inv[i + 1] * (i + 1)) % p;
	}
	return;
}
int C(int n, int m)
{
	if(n < m)
	{
		return 0;
	}
	if(n == m || m == 0)
	{
		return 1;
	}
	return ((fac[n] * inv[m]) % p * inv[n - m]) % p;
}
signed main()
{
	scanf("%lld%lld", &n, &m);
	init();
	printf("%lld", (C(n + m, m) - C(n + m, m - 1) + p) % p);
	return 0;
}