文档章节

CF559C Gerald and Giant Chess

o
 osc_d0mluysz
发布于 2019/04/23 08:21
字数 1188
阅读 8
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

题意

<div class="problem-statement"><div class="header"><div class="title">C. Gerald and Giant Chess</div><div class="time-limit"><div class="property-title">time limit per test</div>2 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>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 <span class="tex-span"><i>h</i> × <i>w</i></span> 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?</p><p>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.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains three integers: <span class="tex-span"><i>h</i>, <i>w</i>, <i>n</i></span> — the sides of the board and the number of black cells (<span class="tex-span">1 ≤ <i>h</i>, <i>w</i> ≤ 10<sup class="upper-index">5</sup>, 1 ≤ <i>n</i> ≤ 2000</span>). </p><p>Next <span class="tex-span"><i>n</i></span> lines contain the description of black cells. The <span class="tex-span"><i>i</i></span>-th of these lines contains numbers <span class="tex-span"><i>r</i><sub class="lower-index"><i>i</i></sub>, <i>c</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>r</i><sub class="lower-index"><i>i</i></sub> ≤ <i>h</i>, 1 ≤ <i>c</i><sub class="lower-index"><i>i</i></sub> ≤ <i>w</i></span>) — the number of the row and column of the <span class="tex-span"><i>i</i></span>-th cell.</p><p>It is guaranteed that the upper left and lower right cell are white and all cells in the description are distinct.</p></div><div class="output-specification"><div class="section-title">Output</div><p>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 <span class="tex-span">10<sup class="upper-index">9</sup> + 7</span>.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input<div title="Copy" data-clipboard-target="#id0033031123525932915" id="id00650808326573397" class="input-output-copier">Copy</div></div><pre id="id0033031123525932915">3 4 2<br>2 2<br>2 3<br></pre></div><div class="output"><div class="title">Output<div title="Copy" data-clipboard-target="#id006408528490475094" id="id0037787000935650505" class="input-output-copier">Copy</div></div><pre id="id006408528490475094">2<br></pre></div><div class="input"><div class="title">Input<div title="Copy" data-clipboard-target="#id00650558159789177" id="id007184960180199327" class="input-output-copier">Copy</div></div><pre id="id00650558159789177">100 100 3<br>15 16<br>16 15<br>99 88<br></pre></div><div class="output"><div class="title">Output<div title="Copy" data-clipboard-target="#id0037774806554387186" id="id009513265065926075" class="input-output-copier">Copy</div></div><pre id="id0037774806554387186">545732279<br></pre></div></div></div></div>

给出一个h*w的棋盘(h,w<=1e5),其中有n个位置不能走(n<=2000),现在要从左上角走到右下角,每步只能向下或者向右走一步。问有多少种走法?右下角保证可以走到。

分析

参照PoemK的题解。

对于右走x步,下走y步的无限制方案数是C(x+y,y),可以记为C(x,y)。 首先将最右下角也作为一个不能走的位置,最后要求出到达这个位置的合法路径数dp[n]。 对所有不能走的位置排序,先比较行,再比较列。 对于位置i,首先有dp[i]=C(x[i],y[i]); 然后到达i途中不能经过任何一个障碍位置,所以枚举第一个障碍位置。dp[i]=dp[i]−∑dp[k]∗C(k−>i)(ifC(k−>i)>0)

时间复杂度$O(n^2)$

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=2e5,mod=1e9+7;
int add(int x,int y) {return (x+=y)>=mod?x-mod:x;}
int mul(int x,int y) {return (ll)x*y%mod;}
int fpow(int x,int k){
	int re=1;
	for(;k;k>>=1,x=mul(x,x))
		if(k&1) re=mul(re,x);
	return re;
}
int fac[N],ifac[N];
int binom(int n,int m) {return mul(fac[n],mul(ifac[m],ifac[n-m]));}
#define x first
#define y second
pair<int,int> a[N];
int h,w,n,f[N];
int main(){
	fac[0]=ifac[0]=1;
	for(int i=1;i<N;++i){
		fac[i]=mul(fac[i-1],i);
		ifac[i]=fpow(fac[i],mod-2);
	}
	read(h),read(w),read(n);
	for(int i=1;i<=n;++i) read(a[i].x),read(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]=binom(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)
			f[i]=add(f[i],mod-mul(f[j],binom(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x)));
	}
	printf("%d\n",f[n+1]);
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
游戏计时器--Gameclock

Gameclock 是一个相对简单的程序,用来跟踪玩家在玩棋类游戏所花费的时间,提供不同的时钟引擎,包括: (speed chess, fisher chess, board games, or hourglass). 图形界面是基于键盘操作。...

匿名
2013/01/14
565
0
使用ceph-deploy安装时出错

@oscfox 你好,想跟你请教个问题:我现在使用deploy部署执行ceph-deploy new agent4时报错,但是生成ceph.conf文件了,执行ceph-deploy install agent4 agent2 agent1时,又报错,错误如下,...

风之子668
2014/12/24
1.4W
6
多用户企鹅游戏--MTP Target

Mtp Target is a free (as freedom and as free beer) multi-players online action game working on Windows, GNU/Linux and Mac where you fight with and against players. 基于 OpenNel ......

匿名
2009/06/10
993
0
国际象棋存储软件--Scid

Scid ("Shane's Chess Information Database") 是一个象棋数据库软件,支持包括 Windows、Linux、Mac OS 以及 Pocket PC 等。通过这个软件你可以管理一个象棋棋局的数据库,并进行搜索、生成...

匿名
2009/06/28
848
0
Java Online Gaming Real-time Engine

Java based client / server online games engine & API for easy creation/running of real-time multiplayer games. Games include Battleships, Camelot, Checkers, Chess, Connect 4, Do......

匿名
2008/09/17
1.5K
0

没有更多内容

加载失败,请刷新页面

加载更多

汇总你在 Linux 上的命令使用情况

使用合适的命令,你可以快速了解 Linux 系统上使用的命令以及执行的频率。 汇总 Linux 系统上使用的命令只需一串相对简单的命令以及几条管道将它们绑定在一起。当你的历史记录缓冲区保留了最...

osc_bvincwvq
35分钟前
14
0
Hacker News 简讯 2020-08-15

最后更新时间: 2020-08-15 07:01 Welders set off Beirut blast while securing explosives - (maritime-executive.com) 焊工在固定炸药的同时引爆了贝鲁特爆炸 得分:383 | 评论:322 Factor......

FalconChen
今天
24
0
OSChina 周六乱弹 —— 老椅小猫秋乡梦 梦里石台堆小鱼

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @小小编辑 :《MOM》- 蜡笔小心 《MOM》- 蜡笔小心 手机党少年们想听歌,请使劲儿戳(这里) @狄工 :腾讯又在裁员了,35岁以上清退,抖音看到...

小小编辑
今天
125
4
构建高性能队列,你不得不知道的底层知识!

前言 本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的知识。 你好,我是彤哥。 上一节,我们一起学习了如何将递归改写为非递归,其中,用到的数据结构主要是栈。 栈和队列...

彤哥读源码
今天
17
0
Anaconda下安装keras和tensorflow

Anaconda下安装keras和tensorflow 一、下载并安装Anaconda: Anaconda下载 安装步骤: 如果是多用户操作系统选择All Users,单用户选择Just Me 选择合适的安装路径 然后勾选这个,自动配置环境...

Atlantis-Brook
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部