[HNOI 2009]有趣的数列

Description

我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：

(1)它是从1到2n共2n个整数的一个排列{a_i}；

(2)所有的奇数项满足a₁<a₃<…<a_2n-1，所有的偶数项满足a₂<a₄<…<a_2n；

(3)任意相邻的两项a_2i-1与a_2i(1≤i≤n)满足奇数项小于偶数项，即：a_2i-1<a_2i。

现在的任务是：对于给定的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

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

题解

我们把奇项和偶项分别按顺序拿出来，

现在解决的问题就是将$1$~$2n$分别按顺序填入每个项中，要保证奇数项中的数的个数总不小于偶数项中的数个数。

显然就是$Catalan$数了。

对于取模...因为模数$p$不一定是质数，那么就质因数分解。

 //It is made by Awson on 2017.10.28

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

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

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

 #define Abs(x) ((x) < 0 ? (-(x)) : (x))

 using namespace std;

 const int N = ;

 int n, pre[(N<<)+], prime[(N<<)+], tot;

 LL p;

 int cnt[(N<<)+];

 void prepare() {

     for (int i = ; i <= (n<<); i++) {

         if (!pre[i]) prime[++tot] = i;

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

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

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

         }

     }

 }

 void work() {

     scanf("%d%lld", &n, &p);

     prepare();

     for (int i = n+; i <= (n<<); i++) {

         int j = i;

         while (pre[j]) {

             cnt[pre[j]]++; j /= pre[j];

         }

         cnt[j]++;

     }

     for (int i = ; i <= n; i++) {

         int j = i;

         while (pre[j]) {

             cnt[pre[j]]--; j /= pre[j];

         }

         cnt[j]--;

     }

     LL ans = ;

     for (int i = ; i <= (n<<); i++)

         for (int j = ; j <= cnt[i]; j++)

             ans = ans*i%p;

     printf("%lld\n", ans);

 }

 int main() {

     work();

     return ;

 }

秒客网