Description
Yehan is a angry grumpy rabbit, who likes jumping into the hole. This day,Yehan jumps again in the pit at home. Each time, he should jump from the hole at the coordinate (1,1) to (n,m), and he has to jump as the way : he can only jump (x, y) to (x+1, y) or (x, y+1). At his home, some holes are filled with water, he couldn’t jump in them. Yehan wants to know how many different way he could jump. If the paths of two ways are different, Yehan considers they are different.
Input
Multiple test dataThe first line of input contains two numbers n, m (2 <= n, m < 1e5)The second line of input contains a number q, the number of holes (q <= 15)The following q lines, the i-th line contains two numbers xi, yi (1 < x1 < x2 < x3 <……< xq < n) (1 < y1 < y2 < y3 < …… < yq < m)
Output
Output contains one line, the number of ways, because the result is too large, you should mod 1000000007
题意：从（1，1）走到（n，m），其中有些格子有水坑不能走（保证水坑坐标(1 < x1 < x2 < x3 <……< xq < n) (1 < y1 < y2 < y3 < …… < yq < m)，之前没看到这个坑死），问你有多少路径。
思路：对于x*y的方格，从左上走到右下的路径数为：Cxx+y。这个高中组合应该讲过，因为横向必走x步，而且只要这x步确定了那么纵向怎么走必确定（可以自己试试），而横着走有x + y种可能。
所以这道题我们要做的是总路径减去走水坑的路径。走水坑路径和总路径做法一样，但要用容斥。因为这里要组合数取模1e+7，所以还要用到逆元。一开始很傻比直接算逆元，其实这里直接打表阶乘的逆元，具体看下面参考内容。
代码最后是数据。
参考：【逆元】
代码：
#include<cstdio> #include<set> #include<vector> #include<cmath> #include<queue> #include<cstring> #include<algorithm> typedef long long ll; using namespace std; const int maxn = 100000+5; const double INF = 0x3f3f3f3f; const ll MOD = 1000000007; struct node{ int x, y; }p[20]; ll ans, n, m; ll fac[maxn << 1], inv[maxn << 1]; int q; int cmp(node a, node b){ return a.x == b.x? a.y < b.y : a.x < b.x; } ll pmul(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans = (ans * a) % MOD; a = a * a % MOD; b >>= 1; } return ans; } void init(){ //阶乘的逆元 fac[0] = fac[1] = 1; for(ll i = 2; i <= 200000; i++) fac[i] = fac[i - 1] * i % MOD; inv[200000] = pmul(fac[200000], MOD - 2); for(ll i = 200000 - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD; } ll C(ll x, ll y){ //组合逆元 return (fac[y] * inv[y - x] % MOD) * inv[x] % MOD; } void dfs(int id, int pre, ll temp, int times){ ll tmp1, tmp2; times++; tmp1 = (temp * C(p[id].x - p[pre].x, p[id].x - p[pre].x + p[id].y - p[pre].y)) % MOD; tmp2 = (tmp1 * C(n - p[id].x, n - p[id].x + m - p[id].y)) % MOD; if(times & 1) ans = (ans + tmp2) % MOD; else ans = (ans - tmp2) % MOD; for(int i = id + 1; i <= q; i++){ dfs(i, id, tmp1, times); } } int main(){ init(); while(~scanf("%lld%lld", &n, &m)){ scanf("%d", &q); p[0].x = 1, p[0].y = 1; for(int i = 1; i <= q; i++){ scanf("%d%d", &p[i].x, &p[i].y); } ans = 0; for(int i = 1; i <= q; i++){ dfs(i, 0, 1, 0); //now pre mul time } printf("%lld ", ((C(n - 1, n + m - 2) - ans) % MOD + MOD) % MOD); } return 0; } /* input 6122 61753 2 1957 18165 4448 30108 91557 89797 9 11169 5062 30315 34046 37127 36827 44369 50521 62770 58297 64008 62857 79378 67405 88132 86222 89483 87524 74355 52758 12 1193 7922 11316 9175 19053 11037 38189 11344 38317 15083 40095 19756 41161 24874 47120 30594 50188 34496 51327 36374 53291 50539 66554 51069 56766 19695 7 2012 1210 12159 11135 18759 13249 40035 13828 41494 13959 45882 18241 49535 19379 31178 59737 7 698 14597 7306 14856 8198 19316 9000 45862 10879 53006 12002 54423 24634 58820 81872 8035 4 32720 1451 40464 4253 51261 6151 72014 6683 21393 42250 13 422 1192 478 2683 3265 3684 4422 4366 4760 13041 6586 22349 6803 24676 7273 25162 8875 29191 13875 32524 14791 33611 17168 34162 21102 39838 5572 26973 9 1760 697 2106 4583 2141 6788 2438 6790 3811 7301 4293 11943 4607 15554 5164 15929 5529 18282 output 390661224 872660150 97529549 252410050 742624594 697140589 674450439 109291758 */