[COCI2016-2017#4] Osmosmjerka 题解
我们发现对于每个点，只有八个方向，也就是说，最终能得到的字符串只会有 \(8nm\) 个，那我们可以考虑把这些字符串的哈希值求出来，相同的哈希值代表选到相同字符串的一种可能，直接统计即可。
现在的问题就在于，怎么快速地求出这 \(8nm\) 个字符串的哈希值。因为 \(k\) 很大，所以我们不能暴力求。发现我们只关心最后长度为 \(k\) 的字符串的哈希值，所以我们可以考虑用倍增优化求哈希。令 \(Hash_{i, j, k}\) 为在点 \((i, j)\) 处向一个方向延伸 \(2^k\) 个字符后得到的字符串的哈希值，这样，把长度按二进制拆开后，逐个加上为 \(1\) 的位上保存的哈希值就可以了（当然必须要乘上增加的底数）。
我们对每个延伸方向都这么做一遍就可以了。
需要注意的是，如果哈希的时候取模，可能会很慢。这里用的是自然溢出，当然评测机心情不好的时候还是要开 O2 才过（
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#define ULL unsigned long long
using namespace std;
const int N = 505;
const int pa = 13331;
const int mod = 998244853;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
char mp[N][N];
ULL pwa[34];
ULL hasha[N][N][34];
int n, m, K;
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};
ULL vc[2000010];
int top;
int pw2[33];
void solve() {
pw2[0] = 1;
for(int i = 1; i<=30; ++i) {
pw2[i] = pw2[i-1]<<1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
hasha[i][j][0] = (mp[i][j] - 'a' + 1);
}
}
for (int d = 0; d < 8; ++d) {
int tx, ty;
for (int k = 1; k <= 29; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
tx = (i + pw2[k-1] * dx[d] - 1) % n;
ty = (j + pw2[k-1] * dy[d] - 1) % m;
tx = (tx + n) % n + 1;
ty = (ty + m) % m + 1;//求出延伸后的点的坐标
hasha[i][j][k] = (hasha[i][j][k - 1] * pwa[k - 1] + hasha[tx][ty][k - 1]);
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int nowx = i, nowy = j;
ULL tmp = 0;
for (int k = 0; k <= 29; ++k) {
if ((K >> k) & 1) {
tmp = tmp * pwa[k] + hasha[nowx][nowy][k];
nowx = (nowx + pw2[k] * dx[d] - 1) % n;
nowy = (nowy + pw2[k] * dy[d] - 1) % m;
nowx = (nowx + n) % n + 1;
nowy = (nowy + m) % m + 1;
}
}
vc[++top] = tmp;
}
}
}
sort(vc+1, vc+top+1);
long long U = 0;
long long cnt = 0;
for (int i = 1; i <= top; ++i) {
if (i > 0 && vc[i] != vc[i - 1]) {
U += (cnt * cnt);//两个人选出这个字符串都有 cnt 种方案，故共 cnt * cnt 种方案
cnt = 1;
} else {
++cnt;
}
}
U += (cnt * cnt);
long long D = (1ll * top * top);//总方案数
long long g = gcd(U, D);
printf("%lld/%lld\n", U / g, D / g);
}
int main() {
pwa[0] = pa;
for (int i = 1; i <= 32; ++i) {
pwa[i] = pwa[i - 1] * pwa[i - 1];
}
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= n; ++i) {
scanf("%s", mp[i] + 1);
}
solve();
return 0;
}