CodeForces 559C Gerald and Gia （格路+容斥+DP）

CodeForces 559C Gerald and Gia

大致题意：有一个 $ N\times M $ 的网格，其中有些格子是黑色的，现在需要求出从左上角到右下角不经过黑色格子的方案数（模 $ 10^9+7 $ ）

$ solution: $

首先 $ orz $ 鸽王，看一眼就说：“嗯？这不就是一道格路+容斥的小水题吗？”，然后秒切大火题。

这道题主要考验我们如何设置动态规划的状态以保证不重不漏的算好所有情况。上一次我发这类“找基准点”的DP题解应该是POJ 1737 Connected Graph 这两道题都要求我们要精确的计算所有情况，我们都需要去构思一种可以囊括所有情况且不会重复的方案。

这一题首先讲一个基本知识：在一个 $ N\times M $ 的网格里，从左上角到右下角的方案数就是： $ C^{N-1}_{N+M-2} $ ，这个可以很好理解：我们从左上角走到右下角总共会走 $ N+M-2 $ 步，而我们只需要在这些步数里选择有那几步是向下走的即可。然后我们回来分析题目，这道题我们很难直接算，只能循序渐进，也就是用最优子结构来得出最优答案，而且这是完全没有后效性的。但是如果我们将从左上角到每一个格子的方案都求出来，这道题的数据范围就很不友好。不过我们发现它的黑色格子数目很少，于是我们可以反向思考，我们求出它会走过黑色格子的路径，这样就不会去跑一些没用的状态了。我们将黑色格子按照从左上角到右下角的顺序排序，然后以到每一个黑色格子的路径作为状态。但是这样我们发现会严重重复，所以我们必须想办法不重复。

为了不重复我们要顶一个基准点：就是这条路径到达的第一个黑色格子，我们只需要确定这第一个格子接下来的路随便走都没问题，于是我们要求出左上角到每一个黑色格子的不经过其他节点的路径（这不就是一个子问题吗？）于是问题迎刃而解。因为我们有办法求所有的经过黑色格子的路径进而反向得出不经过任何黑色格子的路径数。

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define rg register int

using namespace std;

const int mod=1e9+7;

int h,w,n;

int f[2005];

int jc[200015];

int inv[200015];

struct su{

	int x,y;

	inline bool operator <(su z){

		return x!=z.x?x<z.x:y<z.y;

	}

}a[2005];

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar())) if(ch=='-')sign=1;

	while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();

	return sign?-res:res;

}

inline int C(int x,int y){

	return (ll)jc[x]*inv[x-y]%mod*inv[y]%mod;

}

inline int ksm(ll x,int y){

	rg res=1;

	while(y){

		if(y&1)res=res*x%mod;

		x=x*x%mod; y>>=1;

	}return res;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	h=qr(); w=qr(); n=qr();

	jc[0]=jc[1]=inv[0]=1; rg tot=h+w+1;

	for(rg i=2;i<=tot;++i)

		jc[i]=(ll)jc[i-1]*i%mod;

	inv[tot]=ksm(jc[tot],mod-2);

	for(rg i=tot;i>1;--i)

		inv[i-1]=(ll)inv[i]*i%mod;

	for(rg i=1;i<=n;++i)

		a[i].x=qr(),a[i].y=qr();

	a[n+1].x=h; a[n+1].y=w; sort(a+1,a+n+2);

    for(rg i=1;i<=n+1;++i){

		f[i]=C(a[i].x+a[i].y-2,a[i].x-1);

		for(rg j=1;j<i;++j){

			if(a[i].x<a[j].x||a[i].y<a[j].y)continue;

			f[i]=(f[i]-(ll)f[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x))%mod;

		}

	}printf("%d\n",(f[n+1]+mod)%mod);

	return 0;

}

巴特西

CodeForces 559C Gerald and Gia （格路+容斥+DP）