【BZOJ】【1485】【HNOI2009】有趣的数列

2023-02-21 14:50:22

Catalan数/组合数取模

　　Aha！这题我突然灵光一现就想到Catalan数……就是按顺序安排1~2n这些数（以满足前两个条件）……分配到奇数位置上的必须比偶数位置上的多（要不就不满足第三个条件了）

　　Catalan数可以用C(n,2n)/(n+1)直接求

　　但是这题P不保证是质数感觉很捉急啊= =不会捉啊……然后我也没想到50分的DP，果断滚粗了啊sad QAQ

　　Orz zyf & 盾爷，搬运题解：

假设现在我对于数字 i ，要把他的 j 次方加到答案中去，若k是 i 的一个质因子，那么我只要把任务交给k和i/k就可以了，因为$i^j=k^j*(\frac{i}{k})^j$,轮到算$k$或者$\frac{i}{k}$的时候只要把他的指数+上 j 即可，如果 i 是质数，直接加答案即可，因为最后的答案为整数，那么必定i的指数是正数。

 /**************************************************************

     Problem: 1485

     User: Tunix

     Language: C++

     Result: Accepted

     Time:316 ms

     Memory:24708 kb

 ****************************************************************/

 //BZOJ 1485

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 typedef long long LL;

 const int N=,INF=~0u>>;

 /*******************tamplate********************/

 int n,tot,MOD,p[N],v[N],b[N];

 LL ans=;

 inline LL Pow_mod(LL a,LL b){

     LL r=;

     for(;b;b>>=,a=a*a%MOD) if (b&) r=r*a%MOD;

     return r;

 }

 int main(){

 #ifndef ONLINE_JUDGE

 //  freopen("input.txt","r",stdin);

 //  freopen("output.txt","w",stdout);

 #endif

     n=getint(); MOD=getint();

     F(i,,n<<){

         if (!v[i]) p[++tot]=i;

         F(j,,tot){

             if (i*p[j]>*n) break;

             v[i*p[j]]=p[j];

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

         }

     }

     //ans=(n+2)*(n+3)*...*(n*2)  /（2*3*4*...*n);

     F(i,,n) b[i]=-;

     F(i,n+,n<<) b[i]=;

     D(i,n<<,)

         if (!v[i]) ans=ans*Pow_mod(i,b[i])%MOD;

         else b[v[i]]+=b[i],b[i/v[i]]+=b[i];

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

     return ;

 }

1485: [HNOI2009]有趣的数列

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 777 Solved: 411
[Submit][Status][Discuss]

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

HINT

Source

[Submit][Status][Discuss]

码农公寓