首页 > 代码库 > BZOJ1485: [HNOI2009]有趣的数列

BZOJ1485: [HNOI2009]有趣的数列

2024-07-29 04:23:23   217人阅读

1485: [HNOI2009]有趣的数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 623  Solved: 336
[Submit][Status]

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

HINT

 

Source

 

 题解：
刚开始yy了个n^2的DP，是这样的：
因为要求前一项必须<后一项，并且奇数项<偶数项
那么我们考虑从小到大往数列里填数，则在任何时刻奇数位上的数的个数必须不小于偶数位上的数的个数
f[i][j][k]表示 放到i，奇数位放了j个，偶数位放了k个 （我不会说 i 位可以滚动，k位没用，只是为了方便叙述233）
则
f[i][j][k]=f[i-1][j-1][k]+f[i-1][j][k-1]  j>k
f[i][j][k]=f[i-1][j][k-1]  j=k
应该很好理解，因为奇数的j位必须＜偶数的j位
然后就可以n^2搞了
这个算法可以得到50分
后来没有想出什么优化的方法，然后点开题解看到catalan数瞬间惊呆了。
还是上面的思路，我们把这个过程画到平面直角坐标系上
起点为（0，0）
如果在奇数位上放数 折线 就向 斜上方走一格，否则向右下方走一格
终点为 （2*n，0）
要求 折线必须时刻在x轴上方
这不就是 catalan数在买电影票问题 中的经典问题吗！
答案为C（2*n，n）/（n+1）
 
至此，本题第一部分完成
 
如果模的数是质数，显然就可以逆元乱搞了，但现在模的数不是质数
由于答案一定是整数，所以我们考虑把每个数质因数分解，然后就把除法去掉了
这样做是O(n*logn) 的，对于100W的数据应该可以过
但我们有O(n) 的算法：
 
转自Evil.livE  http://blog.csdn.net/jasonzhu8/article/details/5949622
假设现在我对于数字 i ，要把他的 j 次方加到答案中去，若k是 i 的一个质因子，那么我只要把任务交给k和i/k就可以了，因为i^j=k^j*(i/k)^j,轮到算k或者i/k的时候只要把他的指数+上 j 即可，如果 i 是质数，直接加答案即可，因为最后的答案为整数，那么必定i的指数是正数。
 
找一个数的一个质因子我用了线性筛
然后就神奇的做到了O(n)
具体做法可以看代码：
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 200100014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 using namespace std;23 inline int read()24 {25     int x=0,f=1;char ch=getchar();26     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}27     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}28     return x*f;29 }30 int n,tot,mod,p[maxn],v[maxn],b[maxn];31 ll ans=1;32 inline ll power(ll x,ll y)33 {34     ll t=1;35     for(;y;y>>=1,x=x*x%mod)36      if(y&1)t=t*x%mod;37     return t;38 }39 int main()40 {41     freopen("input.txt","r",stdin);42     freopen("output.txt","w",stdout);43     n=read();mod=read();44     for2(i,2,n<<1)45     {46      if(!v[i])p[++tot]=i;47      for1(j,tot)48       {49           int k=i*p[j];50           if(k>2*n)break;51           v[k]=p[j];52           if(i%p[j]==0)break;53       }54     }55     for2(i,2,n)b[i]=-1;56     for2(i,n+2,n<<1)b[i]=1;57     for3(i,n<<1,2)58     if(!v[i])ans=ans*power(i,b[i])%mod;59     else b[v[i]]+=b[i],b[i/v[i]]+=b[i];60     printf("%lld\n",ans);61     return 0;62 }
View Code

 

BZOJ1485: [HNOI2009]有趣的数列


联系
我们