洛谷 P3200 [HNOI2009]有趣的数列
JDOJ 2130: [HNOI2009]有趣的数列 D1 T3
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的值。
Input
输入文件只包含用空格隔开的两个整数n和P。输入数据保证，50%的数据满足n≤1000，100%的数据满足n≤1000000且P≤1000000000。
Output
仅含一个整数，表示不同的长度为2n的有趣的数列个数mod P的值。
Sample Input
3 10
Sample Output
5
HINT
对应的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）。
Source
最优解声明
题解：
模拟赛T1爆零题。
暴力打表看一下可以发现：这道题当n=1、2、3、4、5时，答案分别等于：1、2、5、14、42......
根据出题人@\(JZYshuraK\)的解说，看到这应该马上看出规律。然而本蒟蒻太菜了
这明明就是卡特兰数么？
所以这道题就变成了求第n项卡特兰数模mod。
根据卡特兰数的递推式，常用的计算卡特兰数的递推公式有以下几种：
\[
f(n)=\sum^{n-1}_{i=0}f(i)\times f(n-i-1)
\]
\[ f(n)=f(n-1)\times \frac{4n-2}{n+1} \]
\[ f(n)=\frac{C^{2n}_n}{n+1} \]
（以上知识不会请自行补习...）
第一个公式的时间复杂度是\(O(n^2)\)的。比暴力好不了多少。
第二个公式和第三个公式用不了，因为模数和除数不一定互质，无法进行乘法逆元的运算。
但其实是可以用的，第三个公式可以通过把组合数展开：
\[
C_n^m=\frac{n!}{m!(n-m)!}
\]
以上是组合数公式。
可以化为：
\[
\frac{C_{2n}^{n}}{n+1}=\frac{(2n)!}{n!\times (n+1)!}
\]
下面就是这个东西如何去取模的问题。
隆重介绍一种分数取模的方法（乘法逆元固然是最常用的）：质因数分解约分法。
很简单，因为上面的都是阶乘，所以有很多相同项是可以被约去的。
所以我们先预处理出一个\(1-2n\)的质数表，然后按这个依次合并就好。
代码：
#include<stdio.h>
#define ll long long
#define int long long
ll n,mod,cnt;
ll ans=1,temp,m;
int prime[1000000<<2],a[1000000<<2];
void euler(int x)
{
for(int i=2;i<=x;i++)
{
if(!a[i])
a[i]=prime[++cnt]=i;
for(int j=1;j<=cnt;j++)
{
if(prime[j]>a[i] || prime[j]>x/i)
break;
a[i*prime[j]]=prime[j];
}
}
}
ll qpow(ll a,ll b)
{
ll ret=1;
while(b>0)
{
if(b&1)
ret=(ret*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ret;
}
signed main()
{
scanf("%lld%lld",&n,&mod);
int p=n*2;
euler(p);
for(int i=1;i<=cnt;i++)
{
temp=0;
m=n*2;
while(m>0)
{
m=m/prime[i];
temp=temp+m;
}
m=n;
while(m>0)
{
m=m/prime[i];
temp=temp-m;
}
m=n+1;
while(m>0)
{
m=m/prime[i];
temp=temp-m;
}
ans=(ans*qpow(prime[i],temp))%mod;
}
printf("%lld",ans);
return 0;
}