落谷、Loj。

Description

定义机动路径为：

没有自环
路径至少包含两个格子
从起点开始每一步都向不远离终点的方向移动

相同地形序列指路径上顺序经过的地形序列。

定义机动路径的权值为相同地形序列的数量之和。

求所有机动路径的权值之和。

Solution

同一类机动路径，他的贡献就是数量的平方 \(\Leftrightarrow\) 答案即本质不同机动路径数量的平方和 \(\Leftrightarrow\) 即两个人走的机动路径形式相同的方案总和。

由于从起点开始每一步都向不远离终点的方向移动这一性质，所以只要我们确定了他移动的 \(x, y\) 方向，那么就可以 \(DP\) 了，因为具有了无后效性。那就枚举一下两个人走的方向。

对于一个人来说，分为左上、左下、右上、右下（一类型）、正上方、正下方、正右方、正左方（二类型）四种状态。

发现一类型包含二类型，所以要简单的容斥一下：

如果两个人都是一类型，那么权值贡献是 \(+\)。
如果两个人 \(1\) 个一类型，\(1\) 个二类型，那么是 \(-\)。
如果两个都是二类型，那么要 \(+\)。

然后当前的 \(f_{a,b,c,d}\) 表示第一个人在 \((a, b)\) ，第二个人在 \((c, d)\)。从起点走到这两个地方的方案数。

把能走的方式处理一下，然后写记搜就行。

复杂度

\(O(64n^2m^2)\)

此题卡常，可以利用 \(work(a, b, c, d) = work(c, d, a, b)\) 的对称性来减小 \(2\) 倍常数

#include <iostream>

#include <cstdio>

#include <cstring>

#define rint register int

using namespace std;

const int N = 31, P = 1e9 + 9;

int n, m, ans, dx[2][3], dy[2][3], cnt[2], f[N][N][N][N], w[3][3][3][3];

char g[N][N];

int inline dp(int a, int b, int c, int d) {

	if (a < 1 || a > n || b < 1 || b > m || c < 1 || c > n || d < 1 || d > m || g[a][b] != g[c][d]) return 0;

	if (~f[a][b][c][d]) return f[a][b][c][d];

	rint &v = f[a][b][c][d] = 1;

	for (rint i = 0; i < cnt[0]; i++)

		for (rint j = 0; j < cnt[1]; j++)

			(v += dp(a - dx[0][i], b - dy[0][i], c - dx[1][j], d - dy[1][j])) %= P;

	return v;

}

void prework(int o, int x, int y) {

	cnt[o] = 0;

	for (int a = -1; a <= 1; a++) {

		if (a && a != x) continue;

		for (int b = -1; b <= 1; b++) {

			if ((b && b != y) || (!a && !b)) continue;

			dx[o][cnt[o]] = a, dy[o][cnt[o]] = b, cnt[o]++;

		}

	}

}

int inline work(int a, int b, int c, int d) {

	if (~w[a + 1][b + 1][c + 1][d + 1]) return w[a + 1][b + 1][c + 1][d + 1];

	prework(0, a, b); prework(1, c, d);

	memset(f, -1, sizeof f);

	int res = 0;

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

		for (rint j = 1; j <= m; j++)

			for (rint k = 1; k <= n; k++)

				for (rint l = 1; l <= m; l++) (res += dp(i, j, k, l)) %= P;

	w[a + 1][b + 1][c + 1][d + 1] = w[c + 1][d + 1][a + 1][b + 1] = res;

	return res;

}

int main() {

	memset(w, -1, sizeof w);

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);

	for (int a = -1; a <= 1; a++) {

		for (int b = -1; b <= 1; b++) {

			if (!a && !b) continue;

			for (int c = -1; c <= 1; c++) {

				for (int d = -1; d <= 1; d++) {

					if (!c && !d) continue;

					if ((a * b && c * d) || (!(a * b) && !(c * d))) (ans += work(a, b, c, d)) %= P;

					else ans = (ans - work(a, b, c, d) + P) % P;

				}

			}

		}

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

BJOI2017 机动训练

Description

Solution

复杂度

最新文章

热门文章