盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

CF 313C Gerald and Giant Chess(组合数学+dp)

题目

源地址:http://codeforces.com/contest/559/problem/C

题意

给定一张H*W的网格图,有N个坏点,求左上角走到右下角对10^9+7取模。
1 ≤ H , W ≤ 10^5, 1 ≤ n ≤ 2000

思路


来自:http://blog.csdn.net/popoqqq/article/details/46121519

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
int h, w, n;
struct node {
int x, y;
}p[2010];
bool cmp(node s, node v) {
if (s.x == v.x) return s.y < v.y;
return s.x < v.x;
}
const int N = 200100;
const ll mod = 1e9 + 7;
ll inv[N], f[N], ff[N], dp[2010];
void init(int n) {
inv[0] = inv[1] = 1;
f[0] = f[1] = 1;
ff[0] = ff[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] * i % mod;
inv[i] = inv[mod % i] * (mod - mod / i) % mod;
ff[i] = ff[i - 1] * inv[i] % mod;
}
}
ll C(int n, int m) {
return (f[n] * ff[m] % mod) * ff[n - m] % mod;
}
int main () {
cin>>h>>w>>n;
init(h + w);
for (int i = 0; i < n; i++) {
scanf("%d%d", &p[i].x, &p[i].y);
p[i].x--, p[i].y--;
}
p[n].x = h - 1, p[n].y = w - 1;
sort(p, p + n + 1, cmp);
for (int i = 0; i <= n; i++) {
dp[i] = C(p[i].x + p[i].y, p[i].x);
for (int j = 0; j < i; j++) {
if (p[j].y > p[i].y) continue;
dp[i] = (dp[i] - C(p[i].x + p[i].y - p[j].x - p[j].y, p[i].x - p[j].x) * dp[j] % mod + mod) % mod;
}
//cout<<dp[i]<<endl;
}
cout<<dp[n]<<endl;
return 0;
}

更新日志

  • 12220472 2015-07-25 05:40:33 SIO__Five# C - Gerald and Giant Chess GNU C++ Accepted 139 ms 4700 KB