首页 > 代码库 > BZOJ 1485: [HNOI2009]有趣的数列
BZOJ 1485: [HNOI2009]有趣的数列
Description
求长度为 \(2n\) 的序列.要求
1. \(a_1<a_3<a_5<...<a_{2n-1}\) .
2. \(a_2<a_4<a_6<...<a_{2n}\) .
3. \(a_{2k-1}<a_{2k} ,1\leqslant k\leqslant n\) .
Sol
\(Catalan\) 数.
我们发现 \(a_{2k}\) 必然要大于它前面的所有奇数项.
如果我们把数字 \(1,2,3,...,2n-1,2n\) 全部列出来,它只有两种决策,一种是放入奇数项,一种是放入偶数项.
我们就可以DP了...
\(f[i][j]\) 表示前 \(i\) 个数,其中 \(j\) 个放入奇数项的方案数.
转移就是 \(f[i][j]=f[i-1][j-1]+f[i-1][j]\) .
不过转移是有条件的,需要满足 \(j \leqslant \left \lfloor \frac {i} {2} \right \rfloor \) .
然后这就是 \(Catalan\) 数的一个应用了,不跨过图上直线 \(y=x\) ,此时只需要令 \(k=\frac {i} {2},j \leqslant k\) 就可以看出来了.
还有一个问题就是 \(p\) 不是质数,在两个数不互质的时候没有逆元,所以我们需要分解质因数来计算,可以用线性筛筛出最小质因子,每次除去就可以统计出来了.
因为每个数的质因子个数不超过 \(logn\) ,所以复杂度 \(O(nlogn)\)
Code
/************************************************************** Problem: 1485 User: BeiYu Language: C++ Result: Accepted Time:660 ms Memory:26680 kb****************************************************************/ #include<cstdio>#include<iostream>using namespace std; typedef long long LL;const int N = 2000005; int n,cnt;LL p,ans;bool b[N];int minp[N],pr[N],c[N]; void Pre(int LIM){ minp[1]=1; for(int i=2;i<=LIM;i++){ if(!b[i]) pr[++cnt]=i,minp[i]=cnt; for(int j=1;j<=cnt && pr[j]*i<=LIM ;j++){ b[pr[j]*i]=1,minp[pr[j]*i]=j; if(i%pr[j]==0) break; } }}LL Pow(LL a,LL b,LL res=1){ for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;return res; }void Add(int x,int v){ while(x>1) c[minp[x]]+=v,x/=pr[minp[x]]; }int main(){ cin>>n>>p; Pre(2*n); // for(int i=1;i<=cnt;i++) cout<<pr[i]<<" ";cout<<endl;// for(int i=1;i<=n;i++) cout<<minp[i]<<" ";cout<<endl; for(int i=n+2;i<=2*n;i++) Add(i,1);// cout<<"qwq"<<endl; for(int i=1;i<=n;i++) Add(i,-1); ans=1; for(int i=1;i<=cnt;i++) ans=ans*Pow(pr[i],c[i])%p; return cout<<ans<<endl,0;}
BZOJ 1485: [HNOI2009]有趣的数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。