2011-0069

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目给定 p < m q < n ，A(0,0),B(p,0),C(m,q),D(m,n) 求从A到D和B到C两条路径不相交的方案数。
如果没有限制条件，从(0,0)到(a,b)的方案数是C(a+b,a),所以不考虑相交的情况的方案数是 C(m+n,n)*C(m+q-p,q)
而每种相交的方案，对应一种 从A到C和从B到D的方案，所以相交的路径方案是 C(m+q,q)*C(m+n-p,n)
所以答案是 C(m+n,n)*C(m+q-p,q) － C(m+q,q)*C(m+n-p,n)
由于m,n都比较小，所以阶乘和阶乘的逆元可以预处理出来，这样可以较快的计算C(a,b)
{{{
#include<cstdio>
#define LL long long
const LL P =100000007;
LL pow(LL a,LL n){
    LL ret=1,t=a;
    for(;n;n>>=1){
        if(n&1)ret=ret*t %P;
        t=(t*t)%P;
    }
    return ret;
}
LL z[128*2048],r[128*2048];
LL C(int m,int n){
    return z[m]*r[m-n]%P*r[n]%P;
}
int main(){
    z[0]=1;r[0]=1;
    for(int i=1;i<=200000;++i){
        z[i]=z[i-1]*i % P;
        r[i]=pow(z[i],P-2);
    }
    int m,n,p,q;
    while(scanf("%d%d%d%d",&m,&n,&p,&q)==4){
        printf("%lld\n",(C(m+n,m)*C(m+q-p,q)%P-C(m+q,m)*C(m+n-p,n)%P +P)%P);
    }
    return 0;
}

}}}
by ZhouYuChen

题目给定 p < m q < n ，A(0,0),B(p,0),C(m,q),D(m,n) 求从A到D和B到C两条路径不相交的方案数。

如果没有限制条件，从(0,0)到(a,b)的方案数是C(a+b,a),所以不考虑相交的情况的方案数是 C(m+n,n)*C(m+q-p,q)

而每种相交的方案，对应一种 从A到C和从B到D的方案，所以相交的路径方案是 C(m+q,q)*C(m+n-p,n)

所以答案是 C(m+n,n)*C(m+q-p,q) － C(m+q,q)*C(m+n-p,n)

由于m,n都比较小，所以阶乘和阶乘的逆元可以预处理出来，这样可以较快的计算C(a,b)

#include<cstdio>
#define LL long long
const LL P =100000007;
LL pow(LL a,LL n){
    LL ret=1,t=a;
    for(;n;n>>=1){
        if(n&1)ret=ret*t %P;
        t=(t*t)%P;
    }
    return ret;
}
LL z[128*2048],r[128*2048];
LL C(int m,int n){
    return z[m]*r[m-n]%P*r[n]%P;
}
int main(){
    z[0]=1;r[0]=1;
    for(int i=1;i<=200000;++i){
        z[i]=z[i-1]*i % P;
        r[i]=pow(z[i],P-2);
    }
    int m,n,p,q;
    while(scanf("%d%d%d%d",&m,&n,&p,&q)==4){
        printf("%lld\n",(C(m+n,m)*C(m+q-p,q)%P-C(m+q,m)*C(m+n-p,n)%P +P)%P);
    }
    return 0;
}

by ZhouYuChen