【组合计数】visit

题目大意

从 \((0,0)\) 开始，每次只可走上下左右一个单位长度，可走重复路，求第 \(T\) 步正好走到 \((n,m)\) 的方案数。

答案要求对 \(MOD\) 取模，\(MOD\) 保证是几个不同质数的乘积。

数据范围

\(1\leq T\leq 100000;-T\leq n,m\leq T;1\leq MOD\leq 10^9+7\)

样例输入

4 10

2 2

样例输出

6

思路

枚举向左走了 \(l\) 步，则向右走了 \(r\) 步，向上走了 \(u\) 步，向下走了 \(d\) 步，依据高考数学中的平均分组问题，答案就是：

\[\frac{A_T^T}{A_l^l\ A_r^r\ A_u^u\ A_d^d}=C_T^l\ C_{T-l}^r\ C_{T-l-r}^u
\]

但是这个式子比较繁琐不好计算，但是聚聚 \(\texttt{skyh}\) 给出了一个简单的式子：

\[C_T^{\frac{T-n-m}{2}}\ C_T^{\frac{T-\vert n-m\vert}{2}}
\]

问了数奥的同学该式子的正确性，请大家学习。

显然使用 \(Lucas\) 定理求解。

噫，好，我会了！

然后一顿怒操作发现样例输出 \(0\)。这是因为在模 \(10\) 的意义下样例是没有逆元的。所以我们需要将模数分解质因子，在每一个质因子下的模意义下求出答案，最后用 \(CRT\) 合并答案即可。

代码

数论全家桶

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=1e5+10;

int T,Mod,N,M;

int res[maxn],fac[maxn],inv[maxn];

inline int read(){

    int x=0;bool fopt=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;

    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;

    return fopt?x:-x;

}

void exgcd(int a,int b,int &x,int &y){

    if(!b)return x=1,y=0,void();

    exgcd(b,a%b,x,y);

    int z=x;x=y;y=z-(a/b)*y;

}

inline int qpow(int x,int b,int p){

    int ans=1,base=x;

    while(b){

        if(b&1)ans=ans*base%p;

        base=base*base%p;

        b>>=1;

    }

    return ans;

}

bool Miller_Rabin(int n){

    if(n==2)

        return true;

    for(int i=1;i<=30;i++){

        int a=rand()%(n-2)+2;

        if(qpow(a,n,n)!=a)

            return false;

    }

    return true;

}

int v[maxn];

inline void Get(int x){

    int u=sqrt(x);

    for(int i=2;i<=u;i++){

        if(x%i!=0)continue;

        if(Miller_Rabin(i)){

            v[++v[0]]=i;

            x/=i;

        }

    }

    if(x>1)v[++v[0]]=x;

}

inline int C(int n,int m,int p){

    if(n<m)return 0;

    if(!m||n==m)return 1;

    return fac[n]*inv[m]%p*inv[n-m]%p;

}

int Lucas(int n,int m,int p){

    if(n<m)return 0;

    if(!m)return 1;

    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;

}

inline int CRT(int n){

    int M=1,ans=0;

    for(int i=1;i<=n;i++)

        M*=v[i];

    for(int i=1;i<=n;i++){

        int m=M/v[i];

        int x=0,y=0;

        exgcd(m,v[i],x,y);

        ans+=res[i]*m*(x<0?x+v[i]:x);

    }

    return ans%M;

}

signed main(){

    srand(time(0));

    T=read();Mod=read();N=read();M=read();

    Get(Mod);

    for(int i=1;i<=v[0];i++){

        int p=v[i];

        fac[0]=fac[1]=inv[0]=inv[1]=1;

        for(int j=2;j<=T;j++)

            inv[j]=(p-p/j)*inv[p%j]%p;

        for(int j=2;j<=T;j++){

            inv[j]=inv[j-1]*inv[j]%p;

            fac[j]=fac[j-1]*j%p;

        }

        res[i]=Lucas(T,(T-N-M)/2,p)*Lucas(T,(T-abs(N-M))/2,p)%p;

    }

    printf("%lld\n",CRT(v[0]));

    return 0;

}

巴特西

【组合计数】visit

题目大意

数据范围

样例输入

样例输出

思路

代码

最新文章

热门文章