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 对应的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）。
解题方法：
http://www.cnblogs.com/beiyuoi/p/5962846.html
http://www.cnblogs.com/hapjin/p/5758083.html
///BZOJ 1485 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 2000005; LL P, ans=1; int n, cnt; bool check[maxn]; int minp[maxn], pr[maxn], c[maxn]; void predeal(int N) { minp[1]=1; for(int i=2; i<= N; i++){ if(!check[i]) pr[++cnt]=i, minp[i]=cnt; for(int j=1; j<=cnt && pr[j]*i<=N; j++){ check[pr[j]*i]=1; minp[pr[j]*i]=j; if(i%pr[j]==0) break; } } } LL powmod(LL a, LL b){ LL res=1; while(b){ if(b&1) res=res*a%P; a=a*a%P; b>>=1; } return res; } void add(int x, int v){ while(x>1){ c[minp[x]]+=v; x/=pr[minp[x]]; } } int main() { scanf("%d%lld", &n,&P); predeal(2*n); for(int i=n+2; i<=2*n; i++) add(i, 1); for(int i=1; i<=n; i++) add(i,-1); for(int i=1; i<=cnt; i++) ans=ans*powmod(pr[i], c[i])%P; printf("%lld\n", ans); return 0; }