文档章节

CF559C Gerald and Giant Chess

o
 osc_kzm1jtt6
发布于 2018/09/12 19:22
字数 634
阅读 37
收藏 0

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

组合数学 + 容斥

首先考虑一下不经过障碍物的情况,从$(1, 1)$到$(n, m)$相当于在$n +m - 2$步中选出$m - 1$步往下走,方案数$\binom{n + m - 2}{m - 1}$。

再考虑一下只有一个障碍物的情况,假设这个障碍物$(x, y)$,那么总的方案数是$\binom{n + m - 2}{m - 1} - \binom{n + m - x - y}{m - y} * \binom{x + y - 2}{y - 1}$。

那么有多个障碍物的情况怎么办呢?

考虑到一个障碍物$(x, y)$只会对$(1, 1) ~ (x, y)$之内的格子产生影响,所以我们可以考虑从容斥,这样子就得到一个类似于dp的东西。

我脑子一抽就写了个反的

设$f_{i}$表示从$(n, m)$走到第$i$个障碍物的方案数,那么有

  $f_{i} = \binom{n + m - x - y}{m - y}$ 

  $f_{i} -= f_{j} * \binom{x' - x + y' - y}{y' - y}$   $(j != i), x \leq x', y \leq y'$(假设$i$的坐标是$(x, y)$,$j$的坐标是$(x', y')$)。

把所有障碍物排序一遍就很好写了。

组合数可以$O(n)$预处理。

时间复杂度$(n^{2})$。

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 2005;
const int M = 2e5 + 5;
const ll P = 1e9 + 7;

int n, m, K;
ll fac[M], inv[M], f[N];

struct Node {
    int x, y;
} a[N];

bool cmp(const Node &u, const Node &v) {
    if(u.x == v.x) return u.y < v.y;
    else return u.x < v.x;
}

inline void read(int &X) {
    X = 0; char ch = 0; int op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline ll pow(ll x, ll y) {
    ll res = 1LL;
    for(; y > 0; y >>= 1) {
        if(y & 1) res = res * x % P;
        x = x * x % P;
    }
    return res;
}

inline ll getC(int x, int y) {
    return fac[x] * inv[y] % P * inv[x - y] % P;
}

int main() {
    read(n), read(m), read(K);
    
    for(int i = fac[0] = 1; i <= n + m; i++) 
        fac[i] = 1LL * fac[i - 1] * i % P;
    inv[n + m] = pow(fac[n + m], P - 2);
    for(int i = n + m - 1; i >= 0; i--)
        inv[i] = 1LL * inv[i + 1] * (i + 1) % P;
    
//    printf("%lld\n", getC(7, 3));
    
    for(int i = 1; i <= K; i++) 
        read(a[i].x), read(a[i].y);
//    a[++K].x = 1, a[K].y = 1;
    sort(a + 1, a + 1 + K, cmp);
      
    ll ans = getC(m + n - 2, m - 1);  
    for(int i = K; i >= 1; i--) {
        f[i] = (f[i] + getC(m + n - a[i].x - a[i].y, m - a[i].y) + P) % P;
        for(int j = i + 1; j <= K; j++) 
            if(a[j].x >= a[i].x && a[j].y >= a[i].y)
                f[i] = (f[i] - f[j] * getC(a[j].x - a[i].x + a[j].y - a[i].y, a[j].y - a[i].y) % P + P) % P;
        ans = (ans - f[i] * getC(a[i].x + a[i].y - 2, a[i].y - 1) % P + P) % P;
    }
    
    printf("%lld\n", ans);
    return 0;
}
View Code

 

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
31分钟前
7
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
3
构建高性能队列,你不得不知道的底层知识!

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

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

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

Atlantis-Brook
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部