题解 P3200 【[HNOI2009]有趣的数列】

· · 题解

一个神奇的题目。。。。

发现前面基本没有讲为什么是卡特兰数的

从题意可以得到，偶数位里面一个偶数要比前面的偶数位大，而这些数位又比和他们对应的奇数位大，所以我们可以得到：对于任意偶数位，这里放的数都大于前面的所有数 换句话说，就算前面所有位置都放尽可能小的数，这个位置最小也就只能放跟它下标一样大的数了（位置4只能放大于等于4的值）

我们转换一下题意，变成1~2n一次放入这个数列里，对于每次放的数要么放在最前的奇数位，要么放在最前的偶数位。

联系前面的结论，我们可以知道：一个数列如果有偶数个数多于奇数个数的情况，就不可能满足条件了。

小证明： (假设有对于2p+1来说刚好偶数位比奇数位多一个，这么最新放的偶数位就是第p+1个，这个偶数位在原来位置就会是2p+2,可是2p+2至少要放一个不小于2p+2的数。。。问题是我们才放到2p+1，所以这种情况不可能有解)

于是答案就是任意位都满足 偶数位个数不超过奇数位个数 的数列的个数

很明显----卡特兰数嘛（好比P1044 栈，典型的卡特兰数，要求就是任意位置出栈<=入栈）

公式Cat n= C^{n}_{2n}/n-1

因为P不一定是质数所以我们要把它分解成若干ci^{pi}相乘的形式。

求出在mod每个ci^{pi}意义下的值。再拓展欧几里得（中国剩余定理）算到一起就是答案了~

只剩下两个问题： 1、m太大，如果是一个质数分解质因子的时候我们O（m）找过去会超时。。

2、我们mod的数也不一定是质数啊。。。

对于1、我们只需要除到sqrt(M),剩下来的就是一个单独的质数因子。（或者就是1,没有质数了）

对于2、因为这是ci^{pi},所以我们只需要把ci分离出来就可以保证互质然后计算，之后再对这些ci处理就好~

都知道C^{m}_{n}=n!/m!/(n-m)!，我们单独看n!,剩下两个方法差不多。

假设n=20,mod=9。我们除去3的倍数，就剩下1,2,4,5,7,8,10,11,13,14,16,17,19,20 因为是mod9意义下，所以10,11,13,14,16,17和1,2,4,5,7,8性质是一样的，那么，我们就可以看成是n/mod个1，2，4，5，7，8相乘，快速幂算出来。

剩下的19，20就单独再算上。

分出来的3,6,9,12,15,18，我们记录下6个3，就可以当作1,2,3,4,5,6再继续算。

对于n!,m!,(n-m)!分别这样弄，我们就可以分别得到两个数A=n!除去ci后的值，B=ci的个数。

因为A一定和mod互质于是我们可以使用逆元代替除，B的话直接加减就好。

最后得到的A、B，A*ci^{B}就是我们要的值。

PS：mod ci^{pi}定义下的逆元是 X^{mod-mod/ci-1}

实现代码：

(PS:这里我组合是直接算的不看ci的情况，然后单独再找ci个数的！)

阶乘：

ll jc(ll n)
{
    if(n==0)return 1;//特判

    ll s=1;
    if(n>=mod)//n<mod就没有必要进行这个计算了
    {   
          for(int i=2;i<mod;i++)if(i%p!=0)s=s*i%mod;
        s=fp(s,n/mod);
    }
    for(int i=2;i<=n%mod;i++)if(i%p!=0)s=s*i%mod;
    return s*jc(n/p)%mod;
}

求组合：


ll C(ll n,ll m)//n!/m!/(n-m)!
{
    return jc(n)*fp(jc(m),mod-mod/p-1)%mod*fp(jc(n-m),mod-mod/p-1)%mod;
}

算最后结果：

ll xx=C(2*n,n),AA=0,BB=0,CC=0;
ll s=p;
while(s<=2*n)//找ci的个数
{
    AA+=2*n/s;
    BB+=n/s;
    CC+=n/s;
    s=s*p;
}
AA-=BB+CC;//xx*p^a=C(2n,n)

拓展欧几里得：


ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        ll xx,yy;
        ll d=exgcd(b,a%b,xx,yy);
        x=yy;
        y=xx-(a/b)*yy;
        return d;
    }
}

AND

if(a1==0&&b1==0)
{
    a1=mod,b1=xx;
    //Xa1+b1=ans
}
else
{
    a2=mod,b2=xx;       
    ll A=a1,B=a2,K=b2-b1,X,Y;//X1a1-X2a2=b2-b1
    exgcd(A,B,X,Y);
    X=X*K;//gcd(a1,a2)=1
    b1=a1*X+b1;
    a1=a1*a2;
    b1=((b1%a1)+a1)%a1;
}

b1就是答案~