「BJOI2017」机动训练 - 容斥原理+动态规划

题目大意

    询问一个棋盘上所有路径形成字符串的等价类包含的数目平方和，在指定了起点与终点后，路径一定不能不朝着终点的方向移动。
    棋盘是八连通的。

---

题目分析

神题。
首先进行一步转化：

对平方的处理：转化为棋盘上两个人合法的走路，路径字符串相同的对数。

继续进行转化，若同时指定起点与终点效率会变低。
根据允许移动方向的性质，不妨将移动的方向分为四类。

1. 向右上方走
2. 向右下方走
3. 向左下方走
4. 向左上方走

在指定了两人的起点后，再指定两人的方向，这样就不需要枚举终点了，然后我们进行Dp：

设置状态$f[x_1,y_1,x_2,y_2]$，表示第一个人在$(x_1,y_1)$，第二个人在$(x_2,y_2)$，朝着指定方向移动的合法字符串对数。

注意到，这样会统计重复，因为只向上，右，下，左走的字符串被重复计算了各一次，故容斥一下排除掉它们即可。

这样我们需要枚举$8\times8$种方向，但由于路径可逆的原因，实际上只进行了$\frac{8\times8}4=16$次Dp。
若忽略转移复杂度，时间复杂度为$O(16n^4)$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=35,mod=1e9+9;

struct pii {
	int x,y;
	pii(int x=0,int y=0):x(x),y(y) {}
};

int n,m,f[maxn][maxn][maxn][maxn],g[3][3][3][3],ans=0;
char map[maxn][maxn];
vector<pii> dxy1,dxy2;

void add(int &x,int v) {
	x+=v;
	if(x>=mod)x-=mod;
}

int Dp(int x1,int y1,int x2,int y2) {
	if(x1<1||x1>n||y1<1||y1>m||x2<1||x2>n||y2<1||y2>m||map[x1][y1]!=map[x2][y2])return 0;
	if(~f[x1][y1][x2][y2])return f[x1][y1][x2][y2];
	f[x1][y1][x2][y2]=1;
	for(pii d1:dxy1)for(pii d2:dxy2)add(f[x1][y1][x2][y2],Dp(x1+d1.x,y1+d1.y,x2+d2.x,y2+d2.y));
	return f[x1][y1][x2][y2];
}

int Solve(int dx1,int dy1,int dx2,int dy2) {
	if(~g[dx1+1][dy1+1][dx2+1][dy2+1])return g[dx1+1][dy1+1][dx2+1][dy2+1];
	dxy1.clear(),dxy2.clear();
	for(int i=-1; i<=1; i++) {
		if(i&&i!=dx1)continue;
		for(int j=-1; j<=1; j++) {
			if((!i&&!j)||(j&&j!=dy1))continue;
			dxy1.push_back(pii(i,j));
		}
	}
	for(int i=-1; i<=1; i++) {
		if(i&&i!=dx2)continue;
		for(int j=-1; j<=1; j++) {
			if((!i&&!j)||(j&&j!=dy2))continue;
			dxy2.push_back(pii(i,j));
		}
	}
	memset(f,-1,sizeof(f));
	int sum=0;
	for(int sx1=1; sx1<=n; sx1++)
		for(int sy1=1; sy1<=m; sy1++)
			for(int sx2=1; sx2<=n; sx2++)
				for(int sy2=1; sy2<=m; sy2++)
					add(sum,Dp(sx1,sy1,sx2,sy2));
	g[dx1+1][dy1+1][dx2+1][dy2+1]=g[dx2+1][dy2+1][dx1+1][dy1+1]=g[-dx1+1][-dy1+1][-dx2+1][-dy2+1]=g[-dx2+1][-dy2+1][-dx1+1][-dy1+1]=sum;
	return sum;
}

int Solve(int x,int y) {
	int sum=0;
	add(sum,Solve(-1,-1,x,y));
	add(sum,Solve(-1,1,x,y));
	add(sum,Solve(1,-1,x,y));
	add(sum,Solve(1,1,x,y));
	add(sum,mod-Solve(-1,0,x,y));
	add(sum,mod-Solve(1,0,x,y));
	add(sum,mod-Solve(0,-1,x,y));
	add(sum,mod-Solve(0,1,x,y));
	return sum;
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)scanf("%s",map[i]+1);
	memset(g,-1,sizeof(g));
	add(ans,Solve(-1,-1));
	add(ans,Solve(-1,1));
	add(ans,Solve(1,-1));
	add(ans,Solve(1,1));
	add(ans,mod-Solve(-1,0));
	add(ans,mod-Solve(1,0));
	add(ans,mod-Solve(0,-1));
	add(ans,mod-Solve(0,1));
	printf("%d\n",ans);
	return 0;
}