洛谷P3200 [HNOI2009]有趣的数列（Catalan数）

P3200 [HNOI2009]有趣的数列

题目描述

我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：

(1)它是从1到2n共2n个整数的一个排列{ai}；

(2)所有的奇数项满足a1<a3<...<a2n-1，所有的偶数项满足a2<a4<...<a2n；

(3)任意相邻的两项a2i-1与a2i(1<=i<=n)满足奇数项小于偶数项，即：a2i-1<a2i。

现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 mod P的值。

输入输出格式

输入格式：

输入文件只包含用空格隔开的两个整数n和P。输入数据保证，50%的数据满足n<=1000，100%的数据满足n<=1000000且P<=1000000000。

输出格式：

仅含一个整数，表示不同的长度为2n的有趣的数列个数mod P的值。

输入输出样例

输入样例#1：

3 10

输出样例#1：

5

对应的5个有趣的数列分别为（1,2,3,4,5,6），（1,2,3,5,4,6），（1,3,2,4,5,6），（1,3,2,5,4,6），（1,4,2,5,3,6）。

/*

    裸的卡特兰数。。。。

    公式：C(n,2*n)/(n+1)%p

    C(n,2*n)表示在2*n个数中选n个，就是组合数啦。。。

    公式可以展开：((2*n)！/n!*(n+1)!)%p

    于是出现唯一的难点：取模

    题目中没说p是不是质数。。。

    因为(2*n)！一定能被n!*(n+1)!)整除

    所以对于每一个小于2*n的质因数p来说，(2*n)！中一定存在数量更多的(或一样多)的因数p

    于是可以分解质因数。。。

    这是线性的，可以预处理。。。

    于是此题解决。。。

*/

#include<iostream>

#include<cstdio>

#define LL long long

using namespace std;

LL n,p;

int a[],pri[],cnt=;

LL pow(LL a,LL b){

    LL s=;

    while(b){

        if(b&) s=s*a%p;

        b>>=;

        a=a*a%p;

    }

    return s;

}

int main(){

    LL ans=;

    LL m,s=;

    scanf("%lld%lld",&n,&p);

    for(int i=;i<=n*;i++){//欧拉筛

        if(a[i]==)

            pri[++cnt]=i;

        for(int j=;j<=cnt&&pri[j]*i<=n*;j++){

            a[pri[j]*i]=;

            if(i%pri[j]==) break;

        }

    }

    for(int i=;i<=cnt;i++){

        s=;

        m=*n;

        while(m>){

            m=m/pri[i];

            s=s+m;

        }

        m=n;

        while(m>){

            m=m/pri[i];

            s=s-m;

        }

        m=n+;

        while(m>){

            m=m/pri[i];

            s=s-m;

        }

        ans=ans*pow(pri[i],s)%p;

    }

    printf("%lld\n",ans);

    return ;

}