[HNOI2009]有趣的数列
题目描述
我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：
(1)它是从1到2n共2n个整数的一个排列{ai}；
(2)所有的奇数项满足a1<a3<...<a2n-1，所有的偶数项满足a2<a4<...<a2n；
(3)任意相邻的两项a2i-1与a2i(1<=i<=n)满足奇数项小于偶数项，即：a2i-1<a2i。
现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 mod P的值。
输入输出格式
输入格式：
输入文件只包含用空格隔开的两个整数n和P。输入数据保证，50%的数据满足n<=1000，100%的数据满足n<=1000000且P<=1000000000。
输出格式：
仅含一个整数，表示不同的长度为2n的有趣的数列个数mod P的值。
输入输出样例
输入样例#1：
3 10
输出样例#1：
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）。
考试的一道题目，但是出题人改了题面，考场上写了一个记搜的暴力，然后打表发现是卡塔兰数，然而忘记取模这回事了...
后面再来看这道题的题面，除了全排列减一下枝看不出怎么写暴力。
50分代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define lll long long
using namespace std;
lll read()
{
lll x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
lll n,p,ans;
lll dp[1000010];
lll f[2010][2010];
lll dfs(lll qian,lll zhi)
{
if(zhi==0) return 1;
if(f[qian][zhi]!=-1) return f[qian][zhi];
if(qian==0||qian==zhi)
{
f[qian][zhi]=dfs(zhi,zhi-1)%p;
return f[qian][zhi];
}
else
{
f[qian][zhi]=(dfs(qian,zhi-1)%p+dfs(qian-1,zhi)%p)%p;
return f[qian][zhi];
}
}
int main()
{
memset(f,-1,sizeof(f));
n=read();p=read();
dp[1]=1;
if(n<=2000) cout<<dfs(0,n)%p;
else
{
for(lll i=2;i<=n;i++)
{
dp[i]=(dp[i-1]*((4*i)%p-2)/(i+1))%p;
}
cout<<dp[n]%p;
}
return 0;
}
这道题的难点在于如何取模，由卡塔兰数必然是整数的性质，我们筛出数据范围内所有的质数，对于每一个和数，记录和数是由哪个质数筛出来的。将分子分母相同的质数数量直接减去，由性质，我们可以知道减出来的个数一定>=0。最后我们直接用快速幂求和即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define lll long long
using namespace std;
lll read()
{
lll x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
lll n,p,ans;
lll pre[2000010];
lll num[2000010];
lll nop[2000010];
lll prime[500010];
lll quick_pow(lll x,lll k)
{
ans=1;
while(k)
{
if(k&1) ans=ans*x%p;
x=x*x%p;
k/=2;
}
return ans%p;
}
int main()
{
lll m=0;
n=read();p=read();
nop[1]=1;
for(lll i=2;i<=2*n;i++)
{
if(!nop[i]) {prime[++m]=i;pre[i]=i;}
for(lll j=1;j<=m,i*prime[j]<=2*n;j++)
{
nop[i*prime[j]]=1;pre[i*prime[j]]=prime[j];
if(i%prime[j]==0) break;
}
}
for(lll i=2;i<=n;i++)
{
lll ii=i;
while(ii!=1)
num[pre[ii]]--,ii/=pre[ii];
}
for(lll i=n+2;i<=2*n;i++)
{
lll ii=i;
while(ii!=1)
num[pre[ii]]++,ii/=pre[ii];
}
lll sum=1;
for(lll i=1;i<=m;i++)
{
if(num[prime[i]])
sum=(sum*quick_pow(prime[i],num[prime[i]]))%p;
}
cout<<sum%p;
}