自动搬运

查看原文

来自洛谷，原作者为

	zhangshiyan 这个家伙很勤劳，什么也没有留下 | ENFJ-A | 可互关 （信誉良好）| CS2 完美D+ | IP属地: 福建 | 现役 OIer，服役 FZSZ

搬运于2025-08-24 22:30:49，当前版本为作者最后更新于2024-11-14 20:38:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P7538 [COCI2016-2017#4] Osmosmjerka

R188752538 记录详情

Main Idea

给定一个字符矩阵，我们将这个矩阵无限复制，形成一个无限大的矩阵。然后，从矩阵中的任意位置出发，可以沿着八个方向（上下左右以及四个斜对角方向）选取连续的 $K$ 个字符，形成一个字符串。题目要求计算，随机选择两个位置和两个方向，得到两个相同的字符串的概率。

Solution

枚举起点 $i$ 和 $j$ 和八个方向 $d$，于是考虑计算哈希值，由于 $2 \leq K \leq 10^9$，数据太大了，于是可以考虑倍增计算哈希值。

我们发现对于每个点，只有八个方向，最终能得到 $8 \times n \times m$ 个字符串，不是很多，那我们可以考虑求出这些字符串的哈希值，相同的哈希值代表选到相同字符串的一种可能，直接统计即可。

但是，模数取 $998244353$ 时被卡掉一个点。

你可以选择：

1. 使用双哈希。
2. 使用一些不那么有名的模数。
3. 自然溢出

优化

当你做完后，开心地提交后，发现错了，为什么呢？由于空间复杂度是 $O(8 \times n ^ 2 \times \log_{2}{K})$ 内存超限了，怎么办呢？

肯定是用类似滚动数组的方式来优化空间复杂度，由于八个方向之间的计算互不影响，所以我们分开算八次，优化复杂度为 $O(n ^ 2 \times \log_{2}{K})$ 刚好可以过，具体实现见代码。

当你改完后，开心地提交后，发现还是错了，为什么呢？

注意，如果哈希的时候取模，是很慢。可以用自然溢出或不要再同一行代码取太多了模。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x7ffffff

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + c - '0';
		c = getchar();
	}
	return x * f;
}

const ll mod = 998244853;

char c[505][505];
int st[505][505][50];
ll poww[100];
ll pow2[100];
ll ans[20000010], top;

int dx[10] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[10] = {1, -1, 0, 0, 1, -1, 1, -1};

ll gcd(ll a, ll b)
{
	return !b ? a : gcd(b, a % b);
}

int main()
{
	poww[0] = 133;
	for(int i = 1; i <= 35; i++)
	{
		poww[i] = (poww[i - 1] * poww[i - 1]) % mod;
	}
	pow2[0] = 1;
	for(int i = 1; i <= 35; i++)
	{
		pow2[i] = pow2[i - 1] * 2;
	}
	int n = read(), m = read(), kkk = read();
	for(int i = 0; i < n; i++)
		scanf("%s", c[i]);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			st[i][j][0] = c[i][j] - 'a' + 1;
		}
	}
	for(int k = 0; k < 8; k++)//分开算八次
	{
		for(int l = 1; l <= 30; l++)
		{
			for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < m; j++)
				{
					int x = (i + dx[k] * (pow2[l - 1])) % n;
					int y = (j + dy[k] * (pow2[l - 1])) % m;
					x = (x + n) % n;
					y = (y + m) % m;
					st[i][j][l] = (st[i][j][l - 1] * poww[l - 1] + st[x][y][l - 1]) % mod;
				}
			}
		}
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				ll Hash = 0;
				int x = i, y = j;
				for(int l = 30; l >= 0; l--)
				{
					if(kkk & (1 << l))
					{
						Hash = Hash * poww[l] + st[x][y][l];
						x = (x + pow2[l] * dx[k]) % n;
						y = (y + pow2[l] * dy[k]) % m;
						x = (x + n) % n;
						y = (y + m) % m;
					}
				}
				ans[++top] = Hash;
			}
		}
	}
	sort(ans + 1, ans + top + 1);
	ll cnt = 0;
	ll ans1 = 0;
	ll ans2 = top * top;
	for(int i = 1; i <= top; i++)
	{
		if(i > 1 && ans[i] == ans[i - 1])
		{
			cnt++;
		}
		else
		{
			ans1 += 1LL * cnt * cnt;
			cnt = 1;
		}
	}
	ans1 += cnt * cnt;
	printf("%lld/%lld", ans1 / gcd(ans1, ans2), ans2 / gcd(ans1, ans2));
	return 0;
}