洛谷P1641

洛谷1641

标准卡特兰数的变形问题

${n+m\choose m}-{n+m\choose m-1}$(mn+m​)−(m−1n+m​)

求阶乘+逆元最后求模

阶乘预处理可以使用不过题目只要求一组数值不大所以这个题没啥必要

1.暴力阶乘

#include<iostream>
#define ll long long
using namespace std;
const int mod=20100403;
int n,m;
ll power(ll a,ll b,ll p)
{
	ll ans=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
		{
			ans=(ll)ans*a%p;
		}
		a=(ll)a*a%p;
	}
	return ans;
}
ll C(ll n,ll m)
{
	ll n_=1,m_=1,nm_=1,M,sum;
	for(int i=1;i<=n;i++)
		n_=(n_*i)%mod;
	for(int i=1;i<=m;i++)
		m_=(m_*i)%mod;
	for(int i=1;i<=n-m;i++)
		nm_=(nm_*i)%mod;
	M=(m_*nm_)%mod;
	sum=n_*power(M,mod-2,mod)%mod;
	return sum;
}
int main()
{
	cin>>n>>m;
	cout<<((C(n+m,m)-C(n+m,m-1))%mod+mod)%mod<<endl;
	return 0;
}