CWOI S C0324 C 折纸

题意

U2FsdGVkX18qA6oUQCzTIrtIV0xbZpE8cL3P7ph5HA6Wd8HEuh8O4pWckLxe4zGg
u6tLl6lxQzdOPk5qiB5uqZz3rgJRCb1emkEB1DvBGtF/yLQ6N7J/dCc5vwDPt98C
iSYFcCu1itOs4BFlGDj7M8o4fuTEmQTJ4+0Y5CXJf66xuuaqr0D1CE+fT2u+t+T1
kMWvJ1DmYItj2bRWFZ/PTGWb1HLIPgs2NGCdlbltP32Yf4JITILmzn4Je38gI5/m
3f0POnFnS9kvG8njZgyl4Q==

解析

首先考虑一维的情况。可以把折纸理解成将较短的部分裁掉。令 f(i) 表示是否可以将 0 到 i 裁完，g(i) 表示是否可以将 i 到 n 裁完。答案就是 $\sum_{0 \le i < j \le n} [f(i)=1 \land g(i)=1]$。计算 f(i) 和 g(i) 的过程是类似的。先通过 manacher 算法计算出 h(i) 表示以 i 为回文中心的回文半径，将 f(i) 从 $[i-h(i), i)$ 转移。

对于二维的情况，容易发现，两个维度是独立的，意味着你可以通过哈希转成一维，然后将两个结果乘起来。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using u64 = unsigned long long;

long long solve(const std::vector<u64> &a)
{
	int n = a.size();
	std::vector<int> d(n + 1);
	for (int i = 0, l = 0, r = 0; i <= n; i++) {
		int k = 0;
		if (i <= r) {
			k = std::min(d[l + r - i], r - i);
		}
		while (i - k - 1 >= 0 && i + k < n && a[i - k - 1] == a[i + k]) {
			k++;
		}
		d[i] = k;
		if (i + k > r) {
			l = i - k;
			r = i + k;
		}
	}

	std::vector<bool> f(n + 1), g(n + 1);
	{
		int last = 0;
		f[0] = true;
		for (int i = 1; i <= n; i++) {
			if ((i - last) <= d[i]) {
				f[i] = true;
				last = i;
			}
		}
	}
	{
		int last = n;
		g[n] = true;
		for (int i = n - 1; i >= 0; i--) {
			if ((last - i) <= d[i]) {
				g[i] = true;
				last = i;
			}
		}
	}

	long long ans = 0;
	int sum = 0;
	for (int i = 0; i <= n; i++) {
		if (g[i]) {
			ans += sum;
		}
		sum += f[i];
	}

	return ans;
}

int main()
{
	int n, m;
	std::cin >> n >> m;
	std::vector a(n, std::vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> a[i][j];
		}
	}

	std::vector<u64> h1(n), h2(m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			h1[i] = h1[i] * 233 + a[i][j];
		}
	}
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			h2[j] = h2[j] * 233 + a[i][j];
		}
	}

	std::cout << solve(h1) * solve(h2) << std::endl;
}