1485: [HNOI2009]有趣的数列

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 1284  Solved: 688

[][][]

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

5

 

这道题正着想很不好想，所以我们可以倒过来想。

把[1,2n]的排列当成2n个位置，原数列中每个位置当成一个数x，那么考虑从1到2n依次填现在的每个位置。

然后就很好做了，对于每个奇数的x，填完后一定是有序的，偶数同理，所以可以把奇数视为0，偶数视为1，得到一个合法的01序列后一定可以按顺序还原出数列。

那么当前填了a个0，a+1个1，那么说明原数列中有个位置2i选了，而2i-1还没选，则a[2i-1]>a[2i]，显然是违法的。

因为每个时刻0>1,通项为卡特兰数列。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define ll long long 6 #define N 2000005 7 using namespace std; 8 int n,p; 9 int su[N],tot,pr[N],fan[N];10 const int inf = 2000000;11 void shai()12 {13     for(int i=2;i<=inf;i++)14     {15         if(!pr[i])16         {17             su[++tot]=i;18             fan[i]=tot;19             pr[i]=i;20         }21         for(int j=1;j<=tot&&su[j]<=pr[i]&&su[j]*i<=inf;j++)22         {23             pr[su[j]*i]=su[j];24         }25     }26     return ;27 }28 int num[N];29 inline void fft(int x,int z)30 {31     while(x!=1)32     {33         num[fan[pr[x]]]+=z;34         x/=pr[x];35     }36     return ;37 }38 int main()39 {40     scanf("%d%d",&n,&p);41     shai();42     for(int i=2;i<=n*2;i++)fft(i,1);43     for(int i=2;i<=n;i++)fft(i,-2);44     fft(n+1,-1);45     ll ans=1;46     for(int i=1;i<=tot;i++)47     {48         for(int j=1;j<=num[i];j++)49         {50             ans=ans*su[i]%p;51         }52     }53     printf("%lld\n",ans);54     return 0;55 }