bzoj 1485: [HNOI2009]有趣的数列

题意：

问有多少种$2n$的排列满足奇数项递增、偶数项递增、相邻奇数项$<$偶数项。

题解：

补档
考虑把$1~2n$从小到大放到$2n$个位置上。这样，每次填一个数，要么填在下一个奇数位上，要么填在下一个偶数位上，而对于每一对相邻的奇数偶数位，因为奇数要小于偶数，所以奇数必须先填，也就是说每个时刻填出来奇数的个数要大于等于偶数的个数。这就是卡塔兰数的定义了。因为$p$不是质数不好求逆元，我们可以把$1~2n$分解质因数，算一下答案中每个质因数的指数就好了。

代码：

#include<iostream>
#include<cstring>
#include<map>
#include<vector>
using namespace std;

long long ans=1,n,p;
map<int,int>hh;
bool v[2000010];
int pl[2000010];
vector<int>prime;

void get(int n)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
    {
//        cout<<i<<endl;
        if(!v[i])
        {
            prime.push_back(i);
            pl[i]=i;
        }
//        cout<<"hh"<<endl;
        for(vector<int>::iterator j=prime.begin();j!=prime.end()&&(*j)*i<=n;j++)
        {
            v[(*j)*i]=1;
            pl[(*j)*i]=*j;
            if(i%(*j)==0)
            break;
        }
    }
}
void wk(int x,int y)
{
    while(x!=1)
    {
        hh[pl[x]]+=y;
        x/=pl[x];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>p;
    get(n<<1);
    for(int i=n+2;i<=(n<<1);i++)
    wk(i,1);/*
    for(map<int,int>::iterator it=hh.begin();it!=hh.end();it++)
    cout<<it->first<<' '<<it->second<<endl;*/
    for(int i=2;i<=n;i++)
    wk(i,-1);
    for(map<int,int>::iterator it=hh.begin();it!=hh.end();it++)
    {
        for(int i=0;i<it->second;i++)
        ans=ans*(it->first)%p;
    }
    cout<<ans;
}