裸求卡特兰数（c++）

问题描述：

在一个格点阵列中，从（0，0）点走到（n，n）点且不经过对角线x==y的方法数（x> y）。（要求：对9982357取模）

思路：

对于学过卡特兰数的同学，这就是个裸的求第n个卡特兰数的应用；

对于没有学过卡特兰数的同学，可以自己推导一下符合要求的路径数公式： 下半部分不能穿过但是可以触碰y=x，表示不能触碰y=x+1的非降路径数的一半，从(0,0)到(n,n)的总方法数为，然后减去触碰的路径数，(0,0)对y=x+1取对称点变为(-1,1),(-1,1)到(n,n)的路径数就是走下半部分(0,0)到(n,n)触碰y=x+1的路径，即穿过y=x的路径数。 或者用dp的递推公式推出公式(n*n的复杂度是过不了的) 都得到总路径公式。

需要取模99823357，且求组合数时需要求逆元，但是给出的模数只是长得像素数，并不是素数。

对于学过扩展卢卡斯定理的同学这就是一个裸的扩展卢卡斯定理(卢卡斯定理+中国剩余定理)；

对于没学过的同学，可以根据组合数求出来的结果是整数这一特性先对2n的阶乘的每个乘数的各质因数计数，然后对n和n-1,n+1的阶乘都计数一下最后遍历各质因数用快速幂求出答案。时间复杂度为O(n(nlog(n))^1/2)

法一、质分子分解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=9982357;
ll qpow(ll a, ll n, ll p=mod)
{
    ll re = 1;
    while(n)
    {
        if(n & 1)
            re = (re * a) % p;
        n >>= 1;
        a = (a * a) % p;
    }
    return re % p;
}
vector<int> v;
map<int, int> mp1, mp2, mp3, mp4;
int main()
{

    int n;
    scanf("%d", &n);
    for(int i=2; i<=n-1; i++)
    {
        int x=i;
        for(int j=2; j<=sqrt(x); j++)
        {
            if(x%j==0)
            {
                if(mp4[j]==0)
                {
                    v.push_back(j);
                }
                while(x%j==0)
                {
                    mp1[j]++;
                    mp2[j]++;
                    mp3[j]++;
                    mp4[j]++;
                    x/=j;
                }
            }
        }
        if(x!=1)
        {
            if(mp4[x]==0)
            {
                v.push_back(x);
            }

                mp1[x]++;
                mp2[x]++;
                mp3[x]++;
                mp4[x]++;

        }
    }
    int x=n;
    for(int j=2; j<=sqrt(x); j++)
    {
        if(x%j==0)
        {
            if(mp4[j]==0)
            {
                v.push_back(j);
            }
            while(x%j==0)
            {
                mp2[j]++;
                mp3[j]++;
                mp4[j]++;
                x/=j;
            }
        }
    }
    if(x!=1)
    {
        if(mp4[x]==0)
        {
            v.push_back(x);
        }
        mp2[x]++;
        mp3[x]++;
        mp4[x]++;

    }
    x=n+1;
    for(int j=2; j<=sqrt(x); j++)
    {
        if(x%j==0)
        {
            if(mp4[j]==0)
            {
                v.push_back(j);
            }
            while(x%j==0)
            {
                mp3[j]++;
                mp4[j]++;
                x/=j;
            }
        }
    }
    if(x!=1)
    {
        if(mp4[x]==0)
        {
            v.push_back(x);
        }
        mp3[x]++;
        mp4[x]++;

    }
    for(int i=n+2; i<=2*n; i++)
    {
        int x=i;
        for(int j=2; j<=sqrt(x); j++)
        {
            if(x%j==0)
            {
                if(mp4[j]==0)
                {
                    v.push_back(j);
                }
                while(x%j==0)
                {
                    mp4[j]++;
                    x/=j;
                }
            }
        }
        if(x!=1)
        {
            if(mp4[x]==0)
            {
                v.push_back(x);
            }
            mp4[x]++;

        }
    }
    int res1=1, res2=1;
    for(int i=0; i<v.size(); i++)
    {
        res1=(res1*qpow(v[i], mp4[v[i]]-mp2[v[i]]-mp2[v[i]]))%mod;
    }
    for(int i=0; i<v.size(); i++)
    {
        res2=(res2*qpow(v[i], mp4[v[i]]-mp1[v[i]]-mp3[v[i]]))%mod;
    }

    printf("%d\n", (res1-res2+mod)%mod);

}

法二、扩展卢卡斯：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=9982357;
ll nop=9982357;
ll fac[500005],inv[500005];

ll qpow(ll base,ll k,ll mod)//快速幂运算
{
    ll ans=1;
    while (k) {
        if (k&1)
            ans=ans*base%mod;
        base=base*base%mod;
        k>>=1;
    }
    return ans;
}

ll qmul(ll a,ll b,ll mod)//快速乘法a*b%mod，因为在代码里面运算时，乘法会炸long long
{
    ll ans = 0;
   while(b){
      if(b&1)
         ans = (ans+a)%mod;
       a = (a+a)%mod;
       b >>= 1;
    }
    return ans;
}

void init(ll n,ll m,ll mod)
{
    fac[0]=fac[1]=1;
    for (ll i=2;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[m]=qpow(fac[m],mod-2,mod);
    inv[n-m]=qpow(fac[n-m],mod-2,mod);
}

ll com(ll n,ll m,ll mod)
{
    if (m>n) return 0;
    if (m==n) return 1;
    init(n,m,mod);
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}

ll lucas(ll n,ll m,ll mod)
{
    if (m==0)
        return 1;
    return qmul(lucas(n/mod,m/mod,mod),com(n%mod,m%mod,mod),mod);

}
ll m[15],a[15]; // x≡a[i](mod m[i])
int cnt;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
        x=1,y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return gcd;
}
ll kaven()
{
    ll x,y;
    ll M=m[1],ans=(a[1]%M+M)%M;
    for(int i=2;i<=cnt;i++)
    {
        ll gcd=exgcd(M,m[i],x,y);
        ll c=((a[i]-ans)%m[i]+m[i])%m[i];
        if(c%gcd) return -1;
        x=qmul(x,c/gcd,m[i]/gcd);
        ans+=x*M;
        M*=m[i]/gcd;
        ans=(ans%M+M)%M;
    }
    return ans;
}
int main()
{
    ll n;
    scanf("%lld", &n);
        cnt=0;
        nop=mod;
        for(int i=2; i<=sqrt(nop)+1; i++)
        {
            if(nop%i==0)
            {
                cnt++;
                m[cnt]=i;

                while(nop%i==0)
                {
                    nop/=i;
                }
            }
        }
        if(nop!=1)
        {
            cnt++;
            m[cnt]=nop;
        }
        for(int i=1; i<=cnt; i++)
        {

            a[i]=lucas(2*n, n, m[i]);

        }

        ll res1=kaven();

        for(int i=1; i<=cnt; i++)
        {
            a[i]=lucas(2*n, n-1, m[i]);
        }
        ll res2=kaven();

        printf("%lld\n", (res1-res2+mod)%mod);

}