codeforces 559C Gerald and Giant Chess(dp+组合数学)

- 日理万妓 2021-11-29 14:00 236阅读 0赞

## 题意：给出一个h\*r的矩阵，从左上角走到右下角，中间有一些点不能经过，问不同的路径有多少种。 ##

## 分析：《算法竞赛进阶指南》P335-336。 ##

## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #include<queue>
    #include<cmath>
    using namespace std;
    #define x first
    #define y second
    const int SIZE = 2010;
    pair<int, int> a[SIZE];
    int h, w, n, f[SIZE], mod = 1000000007;
    long long jc[200010], jcinv[200010];
    
    int C(int n, int m) {
    	return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;
    }
    
    long long power(long long a, int b) {
    	long long c = 1;
    	for (; b; b >>= 1) {
    		if (b & 1) c = c*a%mod;
    		a = a*a%mod;
    	}
    	return c;
    }
    
    int main() {
    	jc[0] = 1, jcinv[0] = 1;
    	for (int i = 1; i <= 200000; i++) {
    		jc[i] = jc[i - 1] * i % mod;
    		jcinv[i] = power(jc[i], mod - 2);
    	}
    	cin >> h >> w >> n;
    	for (int i = 1; i <= n; i++)
    		scanf("%d%d", &a[i].x, &a[i].y);
    	sort(a + 1, a + n + 1);
    	a[n + 1].x = h, a[n + 1].y = w;
    	for (int i = 1; i <= n + 1; i++) {
    		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
    		for (int j = 1; j < i; j++) {
    			if (a[j].x > a[i].x || a[j].y > a[i].y) continue;
    			f[i] = (f[i] - (long long)f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x)) % mod;
    		}
    	}
    	cout << (f[n + 1] + mod) % mod << endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces 559C - Gerald and Giant Chess 【计数DP】

题目描述假设虚伪有一个h行w列的棋盘，棋盘上的格子有的是可以经过的，有的是不可以经过的。一开始在棋盘的左上角（第一行第一列）有一颗棋子，这颗棋子每次只能往右或者往下移动一格

迷南。/ 2023年10月11日 13:02/ 0 赞/ 36 阅读

相关 [CF559 C]Gerald and Giant Chess

题面描述给定一个\\(H\W\\)的棋盘，棋盘上只有\\(N\\)个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动

迷南。/ 2023年08月17日 17:38/ 0 赞/ 131 阅读

相关 Codeforces 722E 组合数学 DP

题意：有一个n \ m的棋盘，你初始在点(1, 1)，你需要去点(n, m)。你初始有s分，在这个棋盘上有k个点，经过一次这个点分数就会变为s / 2(向上取整），问从起点到终

冷不防/ 2023年08月17日 17:22/ 0 赞/ 127 阅读

相关 CodeForces 630G-Challenge Pennants【组合数学】

G. Challenge Pennants time limit per test 0.5 seconds memory limit per test 64 megab

矫情吗；*/ 2022年08月21日 04:14/ 0 赞/ 136 阅读

相关 CodeForces 630F-Selection of Personnel【组合数学】

F. Selection of Personnel time limit per test 0.5 seconds memory limit per test 64 m

Myth丶恋晨/ 2022年08月21日 01:28/ 0 赞/ 10 阅读

相关 CodeForces 630H- Benches【组合数学】

H. Benches time limit per test 0.5 seconds memory limit per test 64 megabytes input

太过爱你忘了你带给我的痛/ 2022年08月21日 01:03/ 0 赞/ 172 阅读

相关 ♥CodeForces 609B-B. The Best Gift【组合数学】

B. The Best Gift time limit per test 2 seconds memory limit per test 256 megabytes in

Myth丶恋晨/ 2022年08月19日 11:29/ 0 赞/ 143 阅读

相关 Codeforces 659C Tanya and Toys

Codeforces 659C Tanya and Toys time limit per test 1 second memory limit per test 25

逃离我推掉我的手/ 2022年07月18日 01:48/ 0 赞/ 4 阅读

相关【codeforces】数学

B - B 使用long long Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

素颜马尾好姑娘i/ 2022年07月17日 00:27/ 0 赞/ 137 阅读

相关 codeforces 559C Gerald and Giant Chess(dp+组合数学)

题意：给出一个h\r的矩阵，从左上角走到右下角，中间有一些点不能经过，问不同的路径有多少种。分析：《算法竞赛进阶指南》P335-336。代码： i

- 日理万妓/ 2021年11月29日 14:00/ 0 赞/ 237 阅读