文档章节

Gerald and Giant Chess

o
 osc_6jiql8xy
发布于 2018/12/19 19:55
字数 545
阅读 28
收藏 0

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

link

试题分析

我们发现普通$dp$时间复杂度为$O(h \times w)$的,会$T$的很惨。而这个又无法通过优化,所以呢就要改变$dp$策略。

观察到$n\leq 2000$,所以我们需要设计出一个关于不能走的$dp$。

part1 排列组合应用

$C_i^j$的意思大家都知道把,但是这道题又与排列组合有什么关系呢。易证$C_{n+m}^n$的结果正好是从$(0,0)$走到$(n,m)$的方案数,通过插板法可证。

所以若我们从$(1,1)$出发,到终点$(n,m)$的方案数为$C_{n+m-2}^{n-1}$。

part2 dp

所以说$dp$式子就很好写了,$f(i)$表示只经过$i$号黑点的方案数,其余黑点均不参加。同时将最后所要求的$(h,w)$当作一个黑点。

则:$f(i)={C_{x_i+y_i-2}^{x_i-1}}-f(j)\times C_{x_i-x_j+y_i-y_j}^{x_i-x_j}  (j点在i点的左上角)。$

然后再用逆元求一下即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define int long long
#define mod 1000000007
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int N=200011;
int inv[N],fac[N];
int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans*=a,ans%=mod;
        a*=a,a%=mod;
        b>>=1;
    }return ans%mod;
}
int n,m,k;
struct node{
    int x,y;
}a[N];
int C(int m,int n){if(n==0) return 1;return (fac[m]*((inv[n]*inv[m-n])%mod))%mod;}
bool cmp(node x1,node x2){
    if(x1.x==x2.x) return x1.y<x2.y;
    return x1.x<x2.x;
}
int f[N];
signed main(){
    inv[0]=1,fac[0]=1;
    for(int i=1;i<=200001;i++){
        fac[i]=(fac[i-1]*i)%mod;
        inv[i]=ksm(fac[i],mod-2);
    }
    n=read(),m=read(),k=read();
    for(int i=1;i<=k;i++) a[i].x=read(),a[i].y=read();
    sort(a+1,a+k+1,cmp);
    a[++k].x=n,a[k].y=m;
    for(int i=1;i<=k;i++){
        f[i]=C(a[i].x+a[i].y-2,a[i].x-1)%mod;
        for(int j=1;j<i;j++){
            if(a[j].x>a[i].x||a[j].y>a[i].y) continue;
            f[i]-=f[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x);
            f[i]=((f[i]%mod)+mod)%mod;
        }
    }
    printf("%lld",(f[k]%mod+2*mod)%mod);
}
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

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-08-15

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

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

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

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

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

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

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

Atlantis-Brook
今天
15
0
滴滴ElasticSearch千万级TPS写入性能翻倍技术剖析

桔妹导读:滴滴ElasticSearch平台承接了公司内部所有使用ElasticSearch的业务,包括核心搜索、RDS从库、日志检索、安全数据分析、指标数据分析等等。平台规模达到了3000+节点,5PB 的数据存储...

滴滴技术
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部