正文

$CF559C\ Gerald\ and\ Fiant\ Chess$ 计数类$DP$

IP云
IP云V管理员/1 阅读
08/21
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

AcWing

Description

有个$H$行$W$列的棋盘,里面有$N$个黑色格子,求一个棋子由左上方格子走到右下方格子且不经过黑色格子的方案数.

$1<=H,M<=1e5,1<=N<=2000$.输出对$1e9+7$去模后的结果即可

Sol

假设没有黑色格子,方案数就为$C_{H+W-2}^{H-1}$.

简单说下,可以把向下走看做$0$,向右走看做$1$,其实就是求$01$序列的种数

注意到,黑色格子的总数相当少,所以我们可以把求不经过黑色格子的方案数转化成总方案数减去至少经过一个黑色格子的方案数

在求解计数类$DP$问题时,通常要找到一个"基准点",围绕这个基准点构造一个不可划分的"整体",以避免子问题的重叠.

这句话的意思大概就是找到标准把问题划分为子问题,且这些子问题具有互斥性.

将统计至少经过一个黑色格子的问题转化为枚举每一个黑色格子,并且将以该黑色格子为第一个经过的黑色格子的路径方案数相加.(定语似乎太长了,但是应该都懂的叭)

具体来说,将所有的黑色格子按照行,列坐标递增的顺序排序.第$i$个黑色格子在第$xi$行,$yi$列,设$F[i]$表示从左上角走到第$i$个黑色格子,并且途中不经过其他黑色格子的路线数.

$F[i]=C_{xi-1+yi-1}^{xi-1}-\sum_{j=0}^{i-1}F[j]*C_{xi-xj+yi-yj}^{xi-xj}$,其中$xi>=xj,yi>=yj$

特别地,我们假设左上角的格子为第$0$个黑色格子,右下角的格子为第$N+1$个黑色格子.以$F[0]=1$为初值,$F[n+1]$为答案.

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i<=b;i++)
#define yes(i,a,b) for(Rg int i=a;i>=b;i++)
#define ll long long
using namespace std;
il int read()
{
int x=,y=;char c=getchar();
while(c<''||c>''){if(c=='-')y=-;c=getchar();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
const int N=,M=;
int h,w,n,mod=(1e9)+;
ll f[N],jc[M],inv[M];
struct node{int x,y,s;}a[N];
il bool cmp(node x,node y){if(x.x==y.x)return x.y<y.y;return x.x<y.x;}
il ll ksm(ll x,int y)
{
ll s=;
while(y){if(y&)s=(s*x)%mod;x=(x*x)%mod;y>>=;}
return s;
}
il void init_C()
{
jc[]=,inv[]=;
go(i,,)
jc[i]=jc[i-]*i%mod,inv[i]=ksm(jc[i],mod-);
}
il ll C(int x,int y)
{
return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
h=read(),w=read(),n=read();init_C();
go(i,,n){a[i]=(node){read(),read()},a[i].s=a[i].x+a[i].y;}
a[n+]=(node){h,w,h+w};
sort(a+,a+n+,cmp);
go(i,,n+)
{
f[i]=C(a[i].s-,a[i].x-);
go(j,,i-)
{
if(a[j].x>a[i].x || a[j].y>a[i].y)continue;
f[i]=(f[i]-f[j]*C(a[i].s-a[j].s,a[i].x-a[j].x))%mod;
}
}
printf("%lld\n",(f[n+]+mod)%mod);
return ;
}

随机推荐

  1. 【软件工程】用map 实现把英语文本文件词和个数打印出来

    #include <iostream> #include <fstream> #include <string> #include <map> usin ...

  2. 2016最全的web前端面试题及答案整理

    面试web前端开发,不管是笔试还是面试,都会涉及到各种专业技术问题,今天小编整理了一些常见的web前端面试题及答案,希望对大家有所帮助. 1.常用那几种浏览器测试?有哪些内核(Layout Engin ...

  3. CSS3 动画效果合集

    @charset "UTF-8"; /*! * animate.css -http://daneden.me/animate * Version - 3.5.1 * License ...

  4. 获得android应用的版本号

    在开发的过程中,需要获得版本号 private PackageInfo getVersion() { PackageManager packageManager = MyApplication.get ...

  5. 【原创】leetCodeOj --- Majority Element 解题报告&lpar;脍炙人口的找n个元素数组中最少重复n&sol;2次的元素&rpar;

    题目地址: https://oj.leetcode.com/problems/majority-element/ 题目内容: Given an array of size n, find the ma ...

  6. python笔记之类

    类 python不直接支持私有方式,可以在方法或者属性之前加上双下划线,将其变为私有,即外部无法直接调用 访问私有方法或者属性,方法是: _<类名><变量名> 首先类定义 # ...

  7. 微信中音乐播放在ios不能自动播放解决

    在微信中,ios手机下面音乐被自动禁掉无法自动播放,我们可以执行触发body上的元素,自动进行播放. //音乐 var x = document.getElementById("myAudi ...

  8. Failed to install gems via Bundler

    问题:在执行git push heroku master时,程序报错. 解决办法: 1.bundle update 2.git add . 3.git commit -m "message& ...

  9. Phoenix 5&period;0 hbase 2&period;0 org&period;apache&period;hadoop&period;security&period;authentication&period;util&period;KerberosUtil&period;hasKerberosKeyTab

    <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://mave ...

  10. js之常见问题--for循环中为什么点击总是弹出最后一个i

    首先看看点击不同li标签时,弹出li的索引值对应的结果 HTML: <ul> <li>0</li> <li>2</li> <li&gt ...