BZOJ1485 [HNOI2009]有趣的数列

题面在这里

这题其实是一个裸的卡特兰数……

直接消质因数搞就好了

证明如下:

根据题意,奇数位和偶数位分别递增

则任意选择n个数后,数列就被确定了(或者不合法)

考虑从1到2n依次填入数,则\(2i-1\)\(2i\)两项一定是\(2i-1\)先填

这样就要求已填奇数位个数小于等于已填偶数位个数

就是卡特兰数的经典模型,括号匹配了

之前一直不知道卡特兰数通项公式\(\frac {C_{2n}^n}{n+1}\)是怎么来的,这里再证一下

考虑括号匹配问题,其实就是构造一个长为2n的01串,使得任意位置\(sum_1\le sum_0\)

则先选n个1,方案是\(C_{2n}^n\)

再考虑不合法的方案:必然存在i,使得\(sum1_i=sum0_i+1\)\(sum1_{i-1}=sum0_{i-1}\)

使i+1到2n的01串取反,则整个串有\(n-1\)个0,\(n+1\)个1,对应方案为\(C_{2n}^{n+1}\)

则卡特兰数\(C_{2n}^n-C_{2n}^{n+1}=\frac {C_{2n}^n}{n+1}\)

示例程序:

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
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=2000005;
int n,MOD,p[maxn],nxt[maxn],num[maxn];
bool vis[maxn];
void makep(int n){
for (int i=2;i<=n;i++){
if (!vis[i]) p[++p[0]]=i,nxt[i]=i;
for (int j=1;j<=p[0]&&i*p[j]<=n;j++){
vis[i*p[j]]=1;nxt[i*p[j]]=p[j];
if (i%p[j]==0) break;
}
}
}
inline void add(int x,int f){
for (;x>1;x/=nxt[x]) num[nxt[x]]+=f;
}
int main(){
scanf("%d%d",&n,&MOD);
makep(2*n);
for (int i=n+2;i<=2*n;i++) add(i,1);
for (int i=1;i<=n;i++) add(i,-1);
long long ans=1;
for (int i=1;i<=p[0];i++)
for (int j=1;j<=num[p[i]];j++)
(ans*=p[i])%=MOD;
printf("%lld",ans);
return 0;
}