题面在这里
这题其实是一个裸的卡特兰数……
直接消质因数搞就好了
证明如下：
根据题意，奇数位和偶数位分别递增
则任意选择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;
}
|
