「BZOJ1485」[HNOI2009] 有趣的數(shù)列

?

Description

?我們稱一個(gè)長(zhǎng)度為2n的數(shù)列是有趣的，當(dāng)且僅當(dāng)該數(shù)列滿足以下三個(gè)條件：

???(1)它是從1到2n共2n個(gè)整數(shù)的一個(gè)排列{a_i}；

???(2)所有的奇數(shù)項(xiàng)滿足a₁<a₃<…<a_2n-1，所有的偶數(shù)項(xiàng)滿足a₂<a₄<…<a_2n；

???(3)任意相鄰的兩項(xiàng)a_2i-1與a_2i(1≤i≤n)滿足奇數(shù)項(xiàng)小于偶數(shù)項(xiàng)，即：a_2i-1<a_2i。

???現(xiàn)在的任務(wù)是：對(duì)于給定的n，請(qǐng)求出有多少個(gè)不同的長(zhǎng)度為2n的有趣的數(shù)列。因?yàn)樽詈蟮拇鸢缚赡芎艽?#xff0c;所以只要求輸出答案 mod P的值。

?

Input

輸入文件只包含用空格隔開(kāi)的兩個(gè)整數(shù)n和P。輸入數(shù)據(jù)保證，50%的數(shù)據(jù)滿足n≤1000，100%的數(shù)據(jù)滿足n≤1000000且P≤1000000000。

?

Output

僅含一個(gè)整數(shù)，表示不同的長(zhǎng)度為2n的有趣的數(shù)列個(gè)數(shù)mod P的值。

?

Sample Input

3 10

?

Sample Output

5

?

對(duì)應(yīng)的5個(gè)有趣的數(shù)列分別為（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）。

?

題解

?

對(duì)于 A₄ 來(lái)說(shuō) 它一定大于前三個(gè)

對(duì)于 A₃ 來(lái)說(shuō) 它一定小于后五個(gè)

所以可以推斷 A_I <2*i

可以容易得到一個(gè)n^2的dp

f[i][j]表示前i位填到數(shù)字j的方案，即第i位用的是j

f[i][j]=f[i][j-1]+f[i-1][j-1] (j<=2*i-1)

f[i][j]=f[i][j-1] (j>2*i-1)

輸出前幾項(xiàng)，發(fā)現(xiàn)是個(gè)卡特蘭數(shù)列 ?F(n)=C(2*n,n)/(n+1)

分解質(zhì)因數(shù)求即可

至于為什么是卡特蘭數(shù)列？其實(shí)就是從左往右掃每個(gè)數(shù)，把放在奇數(shù)項(xiàng)看作入棧，偶數(shù)看作出棧

?

50 分 dp

#include<bits/stdc++.h> using namespace std; int n,mod; int f[1005][2005]; int main(){scanf("%d%d",&n,&mod);for(int i=0;i<=2*n;i++) f[0][i]=1;for(int i=1;i<=n;i++)for(int j=1;j<=2*n;j++)if (j<=2*i-1) f[i][j]=(f[i][j-1]+f[i-1][j-1])%mod;else f[i][j]=f[i][j-1]%mod;printf("%d\n",f[n][2*n]);return 0; }

?

?100 分?卡特蘭

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e6+5; ll pri[MAXN],mn[MAXN*2],num[MAXN*2],ans=1; int n,mod,cnt; bool use[MAXN*2]; void getpri(){for (int i=2;i<=2*n;i++){if (!use[i]) pri[++cnt]=i,mn[i]=cnt;for (int j=1;pri[j]*i<=2*n&&j<=cnt;j++){use[pri[j]*i]=1,mn[pri[j]*i]=j;if (i%pri[j]==0) break;}} } void add(int x,int f){while (x!=1){num[mn[x]]+=f;x/=pri[mn[x]];} } int main(){scanf("%d%d",&n,&mod);getpri();for (int i=2*n;i>n;i--) add(i,1);for (int i=1;i<=n;i++) add(i,-1);add(n+1,-1);for (int i=1;i<=cnt;i++) while (num[i]--) ans=(ans*pri[i])%mod;printf("%lld\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/shjrd-dlb/p/9048894.html

總結(jié)

以上是生活随笔為你收集整理的「BZOJ1485」[HNOI2009] 有趣的数列 （卡特兰数列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。