洛谷3200 [HNOI2009]有趣的数列

题解 数学 数学-扩展卢卡斯定理 数学-卡特兰数 省选/NOI-
题目链接 编辑文章

LOJ最优解达成!

题意

求满足下列要求的长度为 $2n$ 的序列 $S$ 的个数,对 $p$ 取模:

  1. 是 $2n$ 的全排列
  2. 奇数项、偶数项分别递增
  3. $\forall i\in [1,n] \ , \ S_{2i-1} < S_{2i}$

题解

对于性质 $2$ ,可以考虑将 $1...2n$ 的数字按照从小到大的顺序依次放入序列。每个数字可以放在最前的奇数或偶数位。

分析性质 $3$ ,显然偶数位上的数比它前面的所有数都大,也就是偶数位 $2i$ 上放的数满足 $S_{2i}\geq 2i$ 。继续分析感觉可以得到放在偶数位的个数应该 $\le$ 奇数位上的个数。

这就是卡特兰数的模型了,答案为 $\dfrac{C_{2n}^n}{n+1}$ 。

将上式转化

$$\dfrac{C_{2n}^n}{n+1} = \dfrac{(2n)!}{(n+1)!\times n!}$$

因为 $p$ 不是质数,没法直接用逆元,所以我直接把 $\text{exLucas}$ 改了一下就交了,然后很开心的得了 $90$ 。

然后发现那组数据的 $p$ 是个 $5e8$ 级别的质数,所以我对剩下的质数进行了特判,如果 $\geq 10^{6}$ 就直接用逆元算。

这种算法在LOJ拿了最优解,洛谷上在第二页,感觉复杂度还是比较优秀。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,p,zs[20005],ans,cnt;
bool ss[100005];

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    ll sqn=sqrt(p);
    for (ll i=2;i<=sqn;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (ll j=1;j<=cnt && zs[j]*i<=sqn;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

ll exgcd(ll l,ll r,ll &x,ll &y)
{
    if (r==0)
    {
        x=1; y=0;
        return l;
    }
    ll ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline ll qpow(ll x,ll y,ll ha)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans%ha;
}

inline ll inv(ll now,ll ha)
{
    ll x=0,y=0;
    exgcd(now,ha,x,y);
    return (x%ha+ha)%ha;
}

inline ll fac(ll x,ll pi,ll pk)
{
    if (!x) return 1;
    ll ans=1;
    for (ll i=2;i<=pk;i++)
    {
        if (i%pi==0) continue;
        ans=ans*i%pk;
    }
    ans=qpow(ans,x/pk,pk);
    ll len=x%pk;
    for (ll i=2;i<=len;i++)
    {
        if (i%pi==0) continue;
        ans=ans*i%pk;
    }
    return ans*fac(x/pi,pi,pk)%pk;
}

inline ll catalan(ll n,ll pi,ll pk)
{
    ll s=0;
    for (ll i=(n<<1);i;i/=pi) s+=i/pi;
    for (ll i=n+1;i;i/=pi) s-=i/pi;
    for (ll i=n;i;i/=pi) s-=i/pi;
    return fac(n<<1,pi,pk)*inv(fac(n+1,pi,pk),pk)%pk*inv(fac(n,pi,pk),pk)%pk*qpow(pi,s,pk)%pk;
}

inline ll C(ll n,ll ha) //ha is prime
{
    ll up=1,down=1;
    for (ll i=n+2;i<=(n<<1);i++) up=up*i%ha;
    for (ll i=n;i;i--) down=down*i%ha;
    return up*inv(down,ha)%ha;
}

inline ll exlucas(ll n)
{
    ll ans=0,p2=p;
    for (ll i=1;i<=cnt;i++)
    {
        if (p2%zs[i]) continue;
        ll pk=1;
        while (p2%zs[i]==0) p2/=zs[i],pk*=zs[i];
        ll ai=catalan(n,zs[i],pk),mi=p/pk;
        ans=(ans+ai*mi%p*inv(mi,pk)%p)%p;
    }
    if (p2>1)
    {
        ll ai=(p2>1e6) ? C(n,p2) : catalan(n,p2,p2),mi=p/p2;
        ans=(ans+ai*mi%p*inv(mi,p2)%p)%p;
    }
    return ans;
}

signed main()
{
    n=read(); p=read();
    get_prime();
    return !printf("%lld",exlucas(n));
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。