今天是情人节，而且今年是永夜抄正式版发行 20 周年 （咏唱组20周年）。
放一张我喜欢的咏唱：
题目描述
我们将一个 \(M\) 行 \(N\) 列的字符矩阵无限复制，可以得到一个无限字符矩阵。例如，对于以下矩阵:
\[\begin{aligned} & \verb!honi! \\ & \verb!hsin! \\ \end{aligned}\]可以无限复制出矩阵
\[\begin{aligned} & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ \end{aligned}\]我们认为矩阵是八连通的。八连通， 指矩阵中的每个位置与上下左右和四个斜向（左上、右上、左下、右下）的位置相邻。因此，从矩阵任意位置出发沿八个方向中的任意一个都可以无限延长。
如果我们随机选择一个位置和一个方向，则可以从此位置开始沿此方向连续选取 \(K\) 个字符组成一个字符串。问，两次这样操作得到两个相同字符串的概率是多少。(假设随机选择时任意位置是等可能的，任意方向也是等可能的)
输入格式
第一行是三个整数 \(M, N, K\)。
接下来 \(M\) 行， 每行一个由小写英文字母组成的长度为 \(N\) 的字符串，即 \(M\times N\) 的字符矩阵。保证矩阵中至少出现两种不同字符。
输出格式
输出一行，为一个化简后的分数，表示概率。
数据范围与提示
- 对于 \(30\%\) 的测试数据：\(M, N ≤ 10\)，\(K ≤ 100\)。
- 对于 \(50\%\) 的测试数据：\(M = N\)。
- 对于 \(100\%\) 的测试数据 ：\(1 ≤ M,N ≤ 500\)，\(2 ≤ K ≤ 10^9\)。
神仙题。
以前只知道二分哈希是好朋友，见过这题后才知道倍增哈希也能一起手牵手。
话说哈希的题好少啊，网上也没什么教程（有也是hash表），明明是这么重要的东西。
最暴力的方法就是枚举全部 $8NM $ 个字符串，然后扔进 map 里。
但字符串长有 \(K\) ，很大。
手玩一下数据（或者观察 \(50\%\) 的点）会发现这个串很快就会出现循环。
特别是 \(M = N\) 这档。
循环节一定不大于 \(N\) 。
于是把循环节和尾巴压一起哈希一下再扔进 map 里。
50 就有了。
那 \(N \neq M\) 呢？
循环节可能有 \(N \times M\) 那么长（算一算会发现是 \(\operatorname{lcm} ( N , M )\)）。
暴力走完是 \(\Theta(N^2M^2)\) 的。
暴力走太慢了，那就快点走。（雾）
遇到 \(10^9 , 10^{18}\) 之类的，要么是个 \(\Theta(1)\) ，要么是个 log 。
考虑一下倍增。
乍一看哈希这东西没法倍增，但别忘了这个东西是有循环节的。
于是就很好搞。
举个例子：
剩下的和一般的倍增差不多。
代码实现
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
using ll=long long;
using ull=unsigned ll;
const int N=505;
int n,m,t;
char ch[N][N];
int dx[]={0,1,0,-1,1,1,-1,-1},dy[]={1,0,-1,0,1,-1,1,-1};
ull h[N][N][8][35],P[35];
ll res,tot;
map<ull,ll>mp;
inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void open_file(){
freopen("genius.in","r",stdin);
freopen("genius.out","w",stdout);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
open_file();
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>ch[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int d=0;d<8;d++)
h[i][j][d][0]=ch[i][j];
P[0]=131;
for(int i=1;i<=32;i++)P[i]=P[i-1]*P[i-1];
for(int k=1;k<=30;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int d=0;d<8;d++){
int x=((i+dx[d]*(1<<(k-1)))%n+n-1)%n+1,
y=((j+dy[d]*(1<<(k-1)))%m+m-1)%m+1;//dx[d]/dy[d]是向 d 方向走了一步，dx[d]/dy[d] *(1<<(k-1)) 就是走 2^(k-1) 步
h[i][j][d][k]=h[i][j][d][k-1]*P[k-1]+h[x][y][d][k-1];//倍增预处理hash
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int d=0;d<8;d++){
ull H=0;//最终的hash值
int x=i,y=j;
for(int k=30;~k;k--)
if((t>>k)&1){//熟悉的倍增
H=H*P[k]+h[x][y][d][k];
x=((x+dx[d]*(1<<k))%n+n-1)%n+1,y=((y+dy[d]*(1<<k))%m+m-1)%m+1;
}
mp[H]++;
tot++;
}
tot*=tot;
//与 tot=8*n*m*8*n*m; 是等价的
for(auto it:mp)res+=it.second*it.second;
ll g=gcd(res,tot);
cout<<res/g<<'/'<<tot/g<<endl;
return 0;
}
//Kirisame Marisa ♥ Alice Margatroid