「BZOJ1485」[HNOI2009] 有趣的数列
Description
我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：
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）。
对应的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）。
题解
如果确定了奇数项，那么数列要么不合法，要么唯一确定
继续观察后发现奇数项只要满足ai<2i即可
可以容易得到一个n^2的dp。。。
f[i][j]表示前i位填到数字j的方案，即第i位用的是j，用前缀和加速转移
输出前几项，发现是个卡特兰数列TAT
然后我就不会求了。。。百度个公式 F(n)=C(2*n,n)/(n+1)
分解质因数求即可
至于为什么是卡特兰数列。。。其实就是从左往右扫每个数，把放在奇数项看作入栈，偶数看作出栈
50分dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define ll long long #define pa pair<int,int> #define mod 1000000007 #define inf 100000000 using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,P; int f[1005][2005],s[1005][2005]; int main() { n=read();P=read(); f[0][0]=1; for(int i=0;i<=2*n;i++)s[0][i]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=2*i-1;j++) { f[i][j]=s[i-1][j-1]%P; } for(int j=1;j<=2*n;j++) s[i][j]=(s[i][j-1]+f[i][j])%P; } printf("%d",s[n][2*n]); return 0; } |
100分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define ll long long #define pa pair<int,int> #define mod 1000000007 #define inf 100000000 using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll ans=1; int n,P,cnt; int pri[1000005],mn[2000005],num[2000005]; bool del[2000005]; void getpri() { for(int i=2;i<=2*n;i++) { if(!del[i])pri[++cnt]=i,mn[i]=cnt; for(int j=1;pri[j]*i<=2*n&&j<=cnt;j++) { del[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() { n=read();P=read(); 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])%P; printf("%d\n",ans); return 0; } |
计数器 9863479
OI 课件=>
OI 课件=>
这。。。