[HNOI2009]有趣的数列 题解（卡特兰数）

[HNOI2009]有趣的数列

Description

我们称一个长度为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的值。

Solution

1.观察下列几种简单情况:

(1)n=1：(1,2);

(2)n=2：(1,2,3,4),(1,3,2,4);

(3)n=3：(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);

可以发现每组中1一定在第一个位置，2n一定在最后一个位置，由数列的性质可以证明；

每组数列都可：增加方案数为n-1;移动上一次2n的位置，增加方案数为1；在此基础上添加2n-1，可以发现2n-1允许插入的范围为n+1,n+2,...,2n-1，由乘法原理知，总方案数为C(2n,n)/n+1;

2.所以本题化简为求解模p剩余系下的卡特兰数，那么通过卡特兰数通项公式化简知c[n]=2n(2n-1).....*(n+2)/n!，易证分子是可以整除分母的，那么统计约分后各个因子个数即可；

3.用线性筛法求出1~2n的mindiv，将分母分子分解质因数；

4.计算各质因数的幂再取模相乘即可；

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int up[200000002],mindiv[20000002],prime[20000002];

long long i,j,k,n,m,p,ans=1;

void oler(long long n){             //线性筛出最小因子和素数表

    for(i=2;i<=n;++i){

        if(!mindiv[i]) prime[++prime[0]]=mindiv[i]=i;

        for(j=1;j<=prime[0]&&prime[j]<=mindiv[i]&&(k=prime[j]*i)<=n;j++) mindiv[k]=prime[j];

    }

    return;

}

void count(){                  //统计因子

    for(i=2*n;i>=n+2;--i){

        k=i;

        while(k>1){

            up[mindiv[k]]++;

            k/=mindiv[k];

        }

    }

    for(i=2;i<=n;++i){

        k=i;

        while(k>1){

            up[mindiv[k]]--;

            k/=mindiv[k];

        }

    }

    return;

}

long long qp(long long x,long long y){          //快速幂

    long long a=1;

    do

    {

        if(y%2==1)a=a*x%p;

        x=x*x%p;

    }

    while(y/=2);

    return a;

}

int main(){

    memset(up,0,sizeof(up));

    memset(mindiv,0,sizeof(mindiv));

    memset(prime,0,sizeof(prime));

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

    oler(n*2);

    count();

    for(i=2;i<=2*n;++i) ans=(ans*qp(i,up[i]))%p;

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

    return 0;

}

特别感谢zzh对本题求解的帮助

卡特兰数基础知识部分可以参考我的题解：http://www.cnblogs.com/COLIN-LIGHTNING/p/8450053.html

[HNOI2009]有趣的数列 题解（卡特兰数）的相关教程结束。