题目描述

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

 

卡特兰数。

可以在网格上模拟（以奇偶为横纵坐标），发现是卡特兰数的推导。

有模数，不需带高精。

现考虑怎样推：

卡特兰数四个公式：

　　1.h(n)=h(0)*h(n-1)+h(1)*h(n-2)+.....h(n-1)*h(0).

　　2.h(n)=C(2n,n)-C(2n,n-1).

　　3.h(n)=C(2n,n)/(n+1)

　　4.h(n)=h(n-1)*(4n+2)/(n+2)

　　

　　现考虑用哪个？？

　　1肯定不行，2会炸时间，4模意义下的p不一定是质数，不能用逆元，也不可。

　　　　3是正解。

　　    一通推导。（第一次算错了，懵了半天）

　　　　有趣的来了，接下来通过质因数分解与快速幂来求解。

　　　　　　通过题解得到至此的思路，接下来的靠阿白了（%%%）。

　　　　　　我一开始想的是每个数都质因数分解，分别记录，最后在统计。这样既费时间，也费空间。

　　　　　　　　正解是（来自阿白的悉心指导）：

　　　　　　　　　　直接开一个数组表示指数，分母为减，分子为加（初状态）， 再通过由大向小递推，统计指数。

　　　　　　　　　　质因数分解需要用到线性筛，会计算到mindiv（最小质因子），再次加以利用。

　　　　　　　　　　妙啊~~~~~~

　　

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int maxn=2000010;
 5 int pri[maxn],mindiv[maxn],num;
 6 int k;
 7 int n,p;
 8 void xxs(){
 9     for(int i=2;i<=2*n;i++){
10         if(!mindiv[i]) mindiv[i]=pri[++num]=i;
11         for(int j=1;j<=num&&((k=i*pri[j])<=2*n)&&pri[j]<=mindiv[i];j++)
12             mindiv[k]=pri[j];
13     }
14 }
15 int zs[maxn];
16 ll ans=1;
17 ll fast_pow(int a,int b){
18     ll s=1;
19     while(b){
20         if(b&1) s=(s*a)%p;
21         a=(a*a)%p;
22         b>>=1;
23     }
24     return s%p;
25 }
26 int main(){
27     scanf("%d%d",&n,&p);
28     xxs();
29     for(int i=1;i<=n;i++) zs[i]=-1;
30     for(int i=n+2;i<=2*n;i++) zs[i]=1;
31     for(int i=2*n;i>=2;i--) if(mindiv[i]!=i)zs[mindiv[i]]+=zs[i],zs[i/mindiv[i]]+=zs[i];//划重点☆☆☆ 
32     for(int i=2;i<=2*n;i++) if(mindiv[i]==i)ans=(ans*fast_pow(i,zs[i])%p)%p; 
33     printf("%lld",ans);
34 //    for(int i=2;i<=n;i++) cout<<i<<" "<<mindiv[i]<<endl;
35 }

View Code