24/02/14 [BJWC2018] 八维

Iictiw / 2024-02-14 / 原文

今天是情人节，而且今年是永夜抄正式版发行 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][35],P[35];
ll res,tot;
map<ull,ll>mp;
inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ch[i][j];
    P[0]=131;
    for(int i=1;i<=32;i++)P[i]=P[i-1]*P[i-1];     
    for(int d=0;d<8;d++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                h[i][j][0]=ch[i][j];
        for(int k=1;k<=30;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++){
                    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][k]=h[i][j][k-1]*P[k-1]+h[x][y][k-1];//倍增预处理hash
                }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                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][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