Osmosmjerka

题目描述

给定一个 $M \times N$ 的字母矩阵，以下面的为例：

honi
hsin

接着我们将其进行无限延伸，得到：

...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...

在无限延伸后得到的新矩阵后，我们随机选取其中一个区域的字母，然后再沿着一定的方向连续读取 $K$ 个字母。在独立完成上述操作两次之后，我们会得到两个长度为 $K$ 的字符串。求两个字符串相同的概率。

题解

令 $f_{x,y,\text{rot},k}$ 表示以 $(x,y)$ 为起点，沿着 $\text{rot}$ 方向走 $k$ 步的字符串哈希值，考虑到 $\text{rot}$ 是冗余的状态，直接舍去， $k$ 用倍增维护。把所有起点的八方向的走 $k$ 步后的字符串的哈希值都加入数组。排一下序就可找出所有相同的字符串的数量。哈希值可以用 unsigned long long 的自然溢出来做。

代码

const int N = 510;

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

namespace Main {
	int rot[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,1},{1,1},{1,-1},{-1,-1}};
	int n, m;
	char s[N][N];
	int p[32];
	ll ans[N * N * 8], cnt, f[N][N][35], len;

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

	int x_, y_;
	void get (int x, int y, int k, int j) {
		x_ = (x + rot[k][0] * (1 << j - 1)) % n; x_ = (x_ - 1 + n) % n + 1;
	    y_ = (y + rot[k][1] * (1 << j - 1)) % m; y_ = (y_ - 1 + m) % m + 1;
	}

	int main () {
		n = Read(), m = Read(), len = Read();
		for (int bin = len, i = 30; i >= 0; i--) 
			if ((1 << i) <= bin) {
				p[i] = 1;
				bin -= 1 << i;
//				puts("DEBUG");
			}
		for (int i = 1; i <= n; i++) scanf ("%s", s[i] + 1);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) f[i][j][0] = (s[i][j] - 'a') + 1;
		}
		for (int k = 0; k < 8; k++) {
			ll t = 37;
			for (int j = 1; j <= 30; j++) {
				if ((1 << j) > len) break;
				for (int x = 1; x <= n; x++)
					for (int y = 1; y <= m; y++) {
						get(x, y, k, j);
						f[x][y][j] = f[x_][y_][j - 1] * t + f[x][y][j - 1];
//						printf ("f:%lld i:%d j:%d x:%d y:%d\n", f[x][y][j], x, y, x_, y_);
					}
				t = t * t;
//				puts("");
			}
			for (int x = 1; x <= n; x++)
				for (int y = 1; y <= m; y++) {
					ll g = 0; 
					x_ = x, y_ = y;
					t = 37;
					for (int j = 0; j <= 30; j++) {
						if (p[j]) {
							g = g * t + f[x_][y_][j];
							get (x_, y_, k, j + 1);
						}
						t = t * t;
					}
					ans[++cnt] = g;
				}
		} 
		sort (ans + 1, ans + 1 + cnt);
		ans[0] = len = 0;
		ll fz = 0, fm = cnt * cnt;
		for (int i = 1; i <= cnt; i++)
			if (ans[i] != ans[i - 1])
				fz += len * len, len = 1;
			else len++;
		fz += len * len;
		ll G = gcd (fz, fm);
		printf ("%lld/%lld\n", fz / G, fm / G);
		return 0;
	}
}

int main () {
//	freopen("genius.in", "r", stdin);
//	freopen("genius.out", "w", stdout);
	Main::main();
	return 0;
}