Codeforces Round #313 (Div. 2) E. Gerald and Giant Chess (Lucas + dp)

题目链接：http://codeforces.com/contest/560/problem/E

给你一个n*m的网格，有k个坏点，问你从(1,1)到(n,m)不经过坏点有多少条路径。

先把这些坏点排序一下。

dp[i]表示从(1,1)到第i个坏点且不经过其他坏点的路径数目。

dp[i] = Lucas(x[i], y[i]) - sum(dp[j]*Lucas(x[i]-x[j], y[i]-x[j])) , x[j] <= x[i] && y[j] <= y[i] //到i点所有的路径数目 - 经过其他点的路径数目

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <ctime>
10 #include <list>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef __int64 LL;
15 typedef pair <int, int> P;
16 const int N = 2e3 + 5;
17 struct Node {
18     LL x, y;
19     bool operator <(const Node &cmp) const {
20         return x == cmp.x ? y < cmp.y : x < cmp.x;
21     }
22 }node[N];
23 LL mod = 1e9 + 7;
24 LL dp[N]; //经过i点不经过其他点的case数
25 LL f[200005]; //阶乘
26 
27 LL Pow(LL a , LL n , LL mod) {
28     LL res = 1;
29     while(n) {
30         if(n & 1)
31             res = res * a % mod;
32         a = a * a % mod;
33         n >>= 1;
34     }
35     return res;
36 }
37 
38 LL Comb(LL a , LL b , LL mod) {
39     if(a < b) {
40         return 0;
41     }
42     if(a == b) {
43         return 1;
44     }
45     return f[a] * Pow(f[a - b] * f[b] % mod, mod - 2, mod) % mod;
46 }
47 
48 LL Lucas(LL n , LL m , LL mod) {
49     LL ans = 1;
50     while(m && n && ans) {
51         ans = (ans * Comb(n % mod , m % mod , mod)) % mod;
52         n /= mod;
53         m /= mod;
54     }
55     return ans;
56 }
57 
58 int main()
59 {
60     f[0] = 1;
61     for(LL i = 1; i <= 200000; ++i) {
62         f[i] = f[i - 1] * i % mod;
63     }
64     LL row, col, sum;
65     int n;
66     scanf("%lld %lld %d", &row, &col, &n);
67     for(int i = 1; i <= n; ++i) {
68         scanf("%lld %lld", &node[i].x, &node[i].y);
69         node[i].x--, node[i].y--;
70     }
71     sort(node + 1, node + n + 1);
72     for(int i = 1; i <= n; ++i) {
73         sum = 0;
74         for(int j = 1; j < i; ++j) {
75             if(node[i].x >= node[j].x && node[i].y >= node[j].y) {
76                 sum = (dp[j]*Lucas(node[i].x + node[i].y - node[j].x - node[j].y, node[i].x - node[j].x, mod) % mod + sum) % mod;
77             }
78         }
79         dp[i] = ((Lucas(node[i].x + node[i].y, node[i].x, mod) - sum) % mod + mod) % mod;
80     }
81     sum = 0;
82     for(int i = 1; i <= n; ++i) {
83         sum = (dp[i]*Lucas(row + col - 2 - node[i].x - node[i].y, row - 1 - node[i].x, mod) % mod + sum) % mod;
84     }
85     printf("%lld
", ((Lucas(row + col - 2, col - 1, mod) - sum) % mod + mod) % mod);
86     return 0;
87 }

View Code