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）。

Solution:

　　本题zyys。

　　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$，由乘法原理知，总方案数为$\frac{C(2n,n)}{n+1}$;

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

　　3.用线性筛法求出$[1,2n]$的$mindiv$（最小质因数），将分母分子分解质因数；

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

代码：

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)>(b)?(b):(a))

using namespace std;

const int N=;

ll n,mod,ans,cnt,prime[N],isprime[N],minn[N],tot[N];

il ll fast(ll s,ll k){

    ll ans=;

    while(k){

        if(k&)ans=ans*s%mod;

        k>>=;

        s=s*s%mod;

    }

    return ans;

}

int main(){

    ios::sync_with_stdio();

    cin>>n>>mod;

    For(i,,n<<){

        if(!isprime[i])prime[++cnt]=i;

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

            isprime[prime[j]*i]=;

            minn[prime[j]*i]=prime[j];

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

        }

    }

    For(i,n+,n<<) {

        int p=i;

        while(minn[p])tot[minn[p]]++,p=p/minn[p];

        tot[p]++;

    }

    For(i,,n) {

        int p=i;

        while(minn[p])tot[minn[p]]--,p=p/minn[p];

        tot[p]--;

    }

    ll ans=;

    For(i,,cnt) ans=ans*fast(prime[i],tot[prime[i]])%mod;

    cout<<ans;

    return ;

}

巴特西

P3200 [HNOI2009]有趣的数列

题目描述

输入输出格式

输入输出样例

最新文章

热门文章