【Codeforces Round #313 (Div. 1) C】 CodeForces 559C Gerald and Giant Chess

2023-11-07 21:33

本文主要是介绍【Codeforces Round #313 (Div. 1) C】 CodeForces 559C Gerald and Giant Chess,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Giant chess is quite common in Geraldion. We will not delve into the
rules of the game, we’ll just say that the game takes place on an
h × w field, and it is painted in two colors, but not like in chess.
Almost all cells of the field are white and only some of them are
black. Currently Gerald is finishing a game of giant chess against his
friend Pollard. Gerald has almost won, and the only thing he needs to
win is to bring the pawn from the upper left corner of the board,
where it is now standing, to the lower right corner. Gerald is so
confident of victory that he became interested, in how many ways can
he win?

The pawn, which Gerald has got left can go in two ways: one cell down
or one cell to the right. In addition, it can not go to the black
cells, otherwise the Gerald still loses. There are no other pawns or
pieces left on the field, so that, according to the rules of giant
chess Gerald moves his pawn until the game is over, and Pollard is
just watching this process.

Input

The first line of the input contains three integers: h, w, n — the
sides of the board and the number of black cells
(1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000).

Next n lines contain the description of black cells. The i-th of these
lines contains numbers ri, ci (1 ≤ ri ≤ h, 1 ≤ ci ≤ w) — the number of
the row and column of the i-th cell.

It is guaranteed that the upper left and lower right cell are white
and all cells in the description are distinct.

Output

Print a single line — the remainder of the number of ways to move
Gerald’s pawn from the upper left to the lower right corner modulo
109 + 7.

计数类dp。
用总方案数减去经过黑格子的方案个数,得到的就是答案。
但是经过黑格子的路径可能经过很多个黑格子,导致重复计算。
于是可以设dp[i]表示从起点到黑点i的合法路径个数,合法路径是说这之前不经过其他黑点。
那么dp[i]=(起点走到点i的路径总数)-∑(dp[j]*(点j到点i的路径总数),点j在点i的左上方)
可以把终点当成一个黑点,他的dp就是答案。
解决两个问题:
1.保证计算点i时,所有在点i左上方的点都计算过。可以通过坐标排序解决。
2.求两点之间的路径总数。
设两点的横、纵坐标之差分别为x,y。
路径总数=C(x,x+y)=(x+y)!/(x!y!)。
因为有除法,所以需要用乘法逆元。
预处理出1..20000的阶乘和其逆元即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long p=1000000007;
long long dp[2010],jc[200100],vjc[200100];
struct node
{int x,y;bool operator < (const node &a) const{return (x<a.x)||(x==a.x&&y<a.y);}
}a[2010];
void eu(long long a,long long b,long long &x,long long &y)
{if (!b){x=1;y=0;}else{eu(b,a%b,y,x);y-=x*(a/b);}
}
void init()
{int i;vjc[0]=jc[0]=1;long long x;for (i=1;i<=200010;i++){jc[i]=(jc[i-1]*i)%p;eu(jc[i],p,vjc[i],x);vjc[i]%=p;vjc[i]+=p;vjc[i]%=p;}
}
long long c(int x,int y)
{return jc[y]*vjc[x]%p*vjc[y-x]%p;
}
int main()
{int i,j,k,m,n,q,x,y,z,h,w;init();scanf("%d%d%d",&h,&w,&n);n++;for (i=1;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);a[n].x=h;a[n].y=w;sort(a+1,a+n+1);for (i=1;i<=n;i++){dp[i]=c(a[i].x-1,a[i].x+a[i].y-2);for (j=1;j<i;j++)if (a[j].y<=a[i].y)dp[i]=((dp[i]-dp[j]*c(a[i].x-a[j].x,a[i].x-a[j].x+a[i].y-a[j].y)%p)+p)%p;}printf("%lld\n",dp[n]);
}

这篇关于【Codeforces Round #313 (Div. 1) C】 CodeForces 559C Gerald and Giant Chess的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/366401

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There