[HNOI2009]有趣的数列

题目

求\(1\)到\(2n\)的全排列种类数，满足奇数项和偶数项分别单增，任意\(a_{2i-1} < a_{2i}\)

思路

（以下为乱搞。。）考虑从1开始考虑每个数字怎么填，可以看（猜）出，由于相邻偶数项比奇数项大，所以奇数项一定要小一些，所以奇数项填的数字个数一定始终大于等于偶数项，这就是个卡特兰数啦

问题变成求\(Catlan(n)\%p\)，由于\(p\)不是质数，需要特殊处理

我会扩展卢卡斯！

由于分子一定整除分母，将分子分母的每种质因子都提出来做减法，再用快速幂乘起来就好了

通过线性筛和倒叙递推可以做到\(O(n)\)求出所有质因子的数量，具体见代码

整个代码的时间复杂度为\(O(nlogn)\)

#include<bits/stdc++.h>
#define N 2000005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,sum[N];
int p[N],mi[N],cnt;
ll mod;

ll quickpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
void init(int maxn)
{
    for(int i=2;i<=maxn;++i)
    {
        if(!mi[i]) p[++cnt]=i,mi[i]=i;
        for(int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
        {
            mi[p[j]*i]=p[j];
            if(i%p[j]==0) break;
        }
    }
}
int main()
{
    cin>>n>>mod;
    init(n<<1);
    for(int i=1;i<=n;++i) sum[i]--;
    for(int i=n+2,t=(n<<1);i<=t;++i) sum[i]++;
    for(int i=2*n;i>=2;--i)//下传标记 
    {
        if(mi[i]!=i)//合数 
        {
            sum[mi[i]]+=sum[i];
            sum[i/mi[i]]+=sum[i];
        }
    }
    ll ans=1;
    for(int i=1,t=(n<<1);i<=t;++i) 
      if(mi[i]==i) ans=ans*quickpow(i,sum[i])%mod;
    cout<<(ans%mod+mod)%mod<<endl;
    return 0;
}

[HNOI2009]有趣的数列

原文：https://www.cnblogs.com/Chtholly/p/11734530.html