Description
You are given four positive integers m,n,p,q(p < m and q < n). There are four points A(0,0),B(p,0),C(m,q),D(m,n). Consider the path ffrom A to D and path g from B to C. f and g are always towards and parallel to the positive direction of one axis, and they can only change their direction on integer points(whose coordinates are both integers).
You are asked to count the number(mod 100000007) of pair (f,g) that f and g have no intersection.
Input
There are multiple cases(less than 100). Each case is a line containing four integers m,n,p,q(m ≤ 100000 and n ≤ 100000).
Output
For each case, output a single line containing the right answer.
Sample Input
2 2 1 1 3 2 1 1
Sample Output
3 6
一开始以为会很多情况。。
结果发现点是有限制的。。。（p < m and q < n）
这样就好做很多。。。
问的是不相交的路线的数目。
不好搞。我们可以求出总的路线的数目，再减去相交的路线的数目。
容易知道 对于一个m*n的矩形网格。
从一个顶点走到对角的顶点的路线数一共有c(m+n,m)种
不妨考虑从（0,0）走到（m,n）
一共需要走m+n段，而这m+n段中，要选择m段横着走。所以是c(m+n,n)
而方案数只 与矩形的尺寸有关，和位置无关。
难点在于相交的路线数。
实际上相交的路线数等价于A到C且B到D的路径数。。。
为什么呢？
首先。。A到C和B到D的路径一定是相交的。。。
其次。。一定会相交在以B C为对角的两个顶点的矩形中（下面称为小矩形）
而且在小矩形的每一个整点处都会相交。。。
而A到D与B到C的路径如果相交，也一定是相交在小矩形中。
而且也是在小矩形的每一个点都会相交。
所以等价。
然后大组合数。。
lucas定理即可。
注意最后mod的是1E8+7...不是1E9+7....
WA了半天。。。SAD。。
适牛教导我说这种mod的直接复制。。。可以不写成1EX+W的形式。。。
现场赛至少检查三遍QAQ
长记性了。
1 /************************************************************************* 2 > File Name: code/zoj/3624.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年10月20日 星期二 06时45分26秒 6 ************************************************************************/ 7 8 #include<iostream> 9 #include<iomanip> 10 #include<cstdio> 11 #include<algorithm> 12 #include<cmath> 13 #include<cstring> 14 #include<string> 15 #include<map> 16 #include<set> 17 #include<queue> 18 #include<vector> 19 #include<stack> 20 #include<cctype> 21 22 #define yn hez111qqz 23 #define j1 cute111qqz 24 #define ms(a,x) memset(a,x,sizeof(a)) 25 using namespace std; 26 const int dx4[4]={1,0,0,-1}; 27 const int dy4[4]={0,-1,1,0}; 28 typedef long long LL; 29 typedef double DB; 30 const int inf = 0x3f3f3f3f; 31 const LL MOD = 1E8+7; 32 int m,n,p,q; 33 LL qpow(LL a,LL b,LL p) 34 { 35 LL res = 1; 36 while (b) 37 { 38 if (b&1) res = (res*a)%p; 39 a = (a*a)%p; 40 b >>=1; 41 } 42 return res; 43 } 44 45 LL comb(LL a,LL b,LL p) 46 { 47 if (a<b) return 0; 48 if (a==b) return 1; 49 if (b>a-b) b = a-b; 50 51 LL ans = 1,ca = 1,cb = 1; 52 for ( LL i = 0 ; i < b ; i++) 53 { 54 ca = (ca*(a-i))%p; 55 cb = (cb*(b-i))%p; 56 } 57 ans = (ca*qpow(cb,p-2,p))%p; 58 return ans; 59 } 60 61 LL lucas(int n,int m,int p) 62 { 63 LL ans = 1; 64 65 while (n&&m&&ans) 66 { 67 ans = (ans*comb(n%p,m%p,p))%p; 68 n /= p; 69 m /= p; 70 } 71 return ans%p; 72 } 73 74 int main() 75 { 76 #ifndef ONLINE_JUDGE 77 freopen("in.txt","r",stdin); 78 #endif 79 80 while (scanf("%d %d %d %d",&m,&n,&p,&q)!=EOF) 81 { 82 LL ans; 83 ans =(lucas(m+n,n,MOD)*lucas(m+q-p,q,MOD))%MOD+MOD; 84 ans = ans -(lucas(m+q,m,MOD)*lucas(m+n-p,n,MOD))%MOD; 85 ans = ans % MOD ; 86 87 88 printf("%lld ",ans); 89 90 } 91 92 93 #ifndef ONLINE_JUDGE 94 fclose(stdin); 95 #endif 96 return 0; 97 }