ZOJ 3624 Count Path Pair(组合计数)
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：从A到D与从B到C的路径中不相交的有多少条。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3624
看似比较复杂，解法也很独特。不相交的难求，那就求相交的。
总路径数是C(M+N,M)*C(Q+M-P,Q)。
然后相交的地方肯定是B与C构成的矩形当中。
我们可以考虑A到C以及B到D，他们的路径必定有相交的，而且相交的位置必定也在矩形当中。
而且相交之后你可以考虑成从A到C的路径改为从交点到D,就样就完成了转化。
结果便是C(M+N,M)*C(Q+M-P,Q)-C(N+M-P,N)*C(M+Q-M);
#include<iostream>#include<fstream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<set>#include<map>#include<queue>#include<stack>#include<string>#include<vector>#include<sstream>#include<ctime>#include<cassert>#define LL long long#define eps 1e-8#define inf 999999.0#define zero(a) abs(a)<eps#define N 20#define MOD 100000007#define pi acos(-1.0)using namespace std;//以下为求逆元LL extend_gcd(LL a,LL b,LL &x,LL &y){ if(b==0){x=1;y=0;return a;} LL gcd=extend_gcd(b,a%b,x,y); LL t=x; x=y;y=t-a/b*x; return gcd;}LL Get_Inverse(LL num){ LL x,y; extend_gcd(num,MOD,x,y); return (x%MOD+MOD)%MOD;}//计算C(N,M)LL cal(LL n,LL m){ LL t1=1,t2=1; for(LL i=n;i>m;i--){ t1=(t1*i)%MOD; t2=(t2*(i-m))%MOD; } return t1*Get_Inverse(t2)%MOD;}int main(){ LL m,n,p,q; while(scanf("%lld%lld%lld%lld",&m,&n,&p,&q)!=EOF) printf("%lld\n",((cal(m+n,m)*cal(q+m-p,q)-cal(n+m-p,n)*cal(m+q,m))%MOD+MOD)%MOD); return 0;}