题目:有趣的数列

描述

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

輸出

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

輸入範例 1

3 10

輸出範例 1

5

輸入範例 2

10 1013

輸出範例 2

588

輸入範例 3

675546 14358205

輸出範例 3

1511390

提示

对于样例1:对应的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)。

50%的数据满足n≤1000 ,100%的数据满足n≤1000000且P≤1000000000。

思路

首先发现它是个卡特兰数

  • 硬算前几项的数字规律(我是这样做的)
  • 可以转换为一个典型的卡特兰数的例子:

    n个数排成两行,使右边都大于左边,后边都大于前边,求排法数量

    将奇数看成第一行,将偶数看成第二行即可。

然后发现数据很大,递推式都有除法,p也不是质数不能用逆元(虽然我也不回逆元我太弱了

所以要用这个通项式

$$ f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1} $$

化一下

$$ f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1} \\ =\frac{(2n)!}{n!\cdot n!\cdot (n+1)}\\ =\frac{(2n)!}{n!\cdot (n+1)!} $$

这样化的作用是可以用特殊的方法约分

枚举1~2n的所有素数

然后分别计算$n,(n+1),2n$中那个素数的次数(cnt1,cnt2,cnt3)

再往答案中乘上$primes_i^{(cnt3-cnt2-cnt1)}$就好了

注意这里是乘不是加我就是这样错的

Code

//I closed myself.What a happy zero-boomed contest!!!
//上一行是考试自闭的时候写的不要管
//(2n)!/(n!*n!*(n+1))
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL MAXN=1000000+5;

LL n,p,cnt;
bool v[MAXN];
LL primes[2*MAXN];
bool isHeshu[2*MAXN];

LL oula(LL x);//质数筛
LL qkpow(LL x,LL y);//快速幂

int main(){
//    freopen("LLeresting.in","r",stdin);
//    freopen("LLeresting.out","w",stdout);
    
    scanf("%d%d",&n,&p);
    oula(2*n);
    LL ans=1;
    for(LL i=1;i<=cnt;++i){
        LL cnt1=0,cnt2=0,cnt3=0;
        LL pm=primes[i];
        while(pm<=2*n){
            cnt1+=n/pm;
            cnt2+=(n+1)/pm;
            cnt3+=2*n/pm;
            pm*=primes[i];//当前质因子次数+1
        }
        LL sl=cnt3-cnt1-cnt2;
        ans*=qkpow(primes[i],sl);
        ans%=p;
    }
    printf("%lld\n",ans);
    
//    fclose(stdin);
//    fclose(stdout);
    return 0;
}

LL oula(LL x){
    for(LL i=2;i<=x;++i){
        if(!isHeshu[i]){
            primes[++cnt]=i;
        }
        for(LL j=1;primes[j]*i<=x;++j){
            isHeshu[primes[j]*i]=1;
            if(i%primes[j]==0)break;
        }
    }
}

LL qkpow(LL x,LL y){
    LL sum=x;
    LL ret=1;
    while(y){
        if(y&1){
            ret=ret*sum%p;
        }
        sum=sum*sum%p;
        y>>=1;
    }
    return ret;
}