【动态规划】【容斥原理】atcoder.jp/contests/dp/tasks/dp_y Grid 2

题目链接：https://atcoder.jp/contests/dp/tasks/dp_y
这题思维难度中等，但似乎是一道很经典的题目，所以记录一下。
假如H或者W不是那么大的话，直接开一个H*W的数组慢慢dp就行了。这里H和W比较大，但是N比较小，看数据范围就知道可能是做一个 $N^2$ 级别的dp。
在图中，如果左上右下两点之间没有阻碍，那么路线数目就是组合数 $C_{y2-y1+x2-x1}^{x2-x1}$ 。
倘若我们定义状态 $dp[i]$ 为从左上角到达第i个障碍点的路径总数。那么，就有一个比较明显的事情：转移的方式一定是从左上到右下的，因为到每个点的路线数和左上的点有关。
但是怎么转移不是很容易想到。这里用到了容斥。普通的容斥是总集合靠着子集和加加减减来求。还有一种容斥用得也不少
$S=A_1+(A_2-A_1∩A_2)+(A_3-(A_1∪A_2)∩A_3)+...+(A_n-(U_1^{n-1}A_i)∩A_n)$
简单来说，就是每次从剩余元素中，把属于 $A_i$ 的取走，直到取完总集合。
那么，考虑 $dp[i]$ ，第i个点的左上角有k个障碍点，我们要求的就是原来的组合数减去经过左上角k个点的路线总数。用经过左上角k个点的路线总数代替上面的S，每一次我们想象依次取走这k个点，每次取的是左上角没有未取障碍点的点。然后把所有经过这个点，但不经过左上的、已经取走的点的路线总数给累计上去。那么我们知道，取走点j时，累计上的数量就是 $dp[j]*C_{yi-yj+xi-xj}^{xi-xj}$ 。
所以，总结一下，首先按x坐标从小到大，x相同y从小到大的顺序给点排序，以满足更新顺序，然后按顺序枚举每个点，先求出原来的无障碍路径数，再把右下角的点给更新一下，减去不经过这个点左上的点的路径总数。
求组合数的话，预处理阶乘，再用求逆元的方法就行了。总复杂度 $O(nlogn+n^2*log(mod))$

#include<cstdio>
#include<algorithm>
#define mo 1000000007
#define x first
#define y second
using namespace std;
using LL=long long;

pair<int,int> P[3005];
int h,w,n,ind[3005],dp[3005],fac[200005];

int quick_power(int a, int b)
{
	int res=1,base=a;
	while(b)
	{
		if(b&1)
			res=(LL)res*base%mo;
		base=(LL)base*base%mo;
		b>>=1;
	}
	return res;
}

int get_C(int a, int b)
{
	return (LL)fac[a]*quick_power(fac[b],mo-2)%mo*quick_power(fac[a-b],mo-2)%mo;
}

int main()
{
	scanf("%d%d%d",&h,&w,&n);
	fac[0]=1;
	for(int i=1;i<=h+w;i++)
		fac[i]=(LL)fac[i-1]*i%mo;
	P[n+1]={h,w};
	for(int i=1;i<=n;i++)
		scanf("%d%d",&P[i].x,&P[i].y);
	n++;
	sort(P+1,P+n+1);
	for(int i=1;i<=n;i++)
		dp[i]=get_C(P[i].x+P[i].y-2,P[i].x-1);
	for(int u=1;u<n;u++)
		for(int j=u+1;j<=n;j++)
			if(P[j].y>=P[u].y)
				dp[j]=(dp[j]-(LL)dp[u]*get_C(P[j].x+P[j].y-P[u].x-P[u].y,P[j].x-P[u].x)%mo+mo)%mo;
	printf("%d",dp[n]);
	return 0;
}

【动态规划】【容斥原理】atcoder.jp/contests/dp/tasks/dp_y Grid 2

相关推荐