链接：https://ac.nowcoder.com/acm/contest/317/H
来源：牛客网

本题考查对卡特兰数的理解。突破点就是2n天恰好写n天作业。

先把问题抽象成：任意位置，不写为-1，写了为+1，要求在任意位置，前缀和大于-k。

当K=1的时候。结果就是卡特兰数。

如图，卡特兰数的几何理解。假设写了为往x轴+1，没写为y+1，任何时刻写了要大于等于没写，所以任意合法路径不能够超过y=x+1这条线。

对于任意不合法路径，将其从第一个不合法的地方开始，把剩余图像关于y=x+1对称。那么要达到的(n,n)就变成了(n-1,n+1)。所以对于任意不合法路径，可以看作一条到(n-1,n+1)的路径。

合法路径的条数就是到（n,n）的条数减去到（n-1，n+1）的条数。也就是C(2n，n)-C(2n，n-1)  （因为有一次横着走变成了竖着走，所以是n-1）

本题对于卡特兰数的几何意义作了推广，把y=x+1变成了y=x+k,所以答案就是C(2n,n)-C(2n,n-k)

这里还有一个考点就是组合数取模，有很多做法，由于P不一定是质数，不一定有逆元，可以套线性筛模板，把组合的质因子和幂处理出来，再快速幂。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+233;
int primes[N], cnt;
ll st[N];
ll sum[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; j < cnt && i * primes[j] <= n; j ++ )
        {
            st[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}
void add(ll x,ll v)
{
    while(st[x])
    {
        sum[st[x]]+=v;
        x/=st[x];
    }
    if(x>0) sum[x]+=v;
}
ll ksm(ll n,ll m,ll p)
{
    ll res=1 %p; //!!!可能取模1
    while(m)
    {
        if(m&1) res=res*n %p;
        n=n*n %p;
        m>>=1;
    }
    return res;
}
ll C(ll n,ll m,ll p)
{
    memset(sum,0,sizeof(sum));
    for(int i=n,j=1;j<=m;j++,i--) add(i,1);
    for(int i=1;i<=m;i++) add(i,-1);
    ll res=1;
    for(int i=2;i<=n;i++)
    {   
        if(sum[i]) res=res*ksm(i,sum[i],p) %p;
    }
    return res;
}
int main()
{
    ll n=0,k=0,p=0;
    cin>>n>>k>>p;
    get_primes(n*2);
    cout<<(C(2*n,n,p)-C(2*n,n+k,p) + p) %p <<endl; //!!取模结果相减可能为负
}