自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

搬运于2025-08-24 22:27:17，当前版本为作者最后更新于2021-04-05 12:22:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解

可以进行行循环移位和列循环移位，因此只需确定左上角的格子是原来的哪个格子，即可确定对应图形。很自然想到将原矩阵复制成左上、右上、左下、右下四份，以方便求解答案。

二维 Hash 可以判断两个子矩阵相不相等，外层套个二分确定第一个不相同的位置，就可以比较字典序大小，总时间复杂度 $O(nm(\log{n}+\log{m}))$。

代码

PS：二维 Hash 可以将 $(i,j)$ 的权值赋为 $p^{(i-1)*m+(j-1)}$（从左到右、从上到下对格子进行编号），也可以将其赋为 $p^{i}q^{j}$（行列分别编号），其中 $p,q$ 为互不相同的质数。笔者使用的是前者，官方题解使用的是后者，故都贴一下代码。

笔者代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int inv2=5e8+4;
inline int get_sum(int a,int b)
{
	return a+b-(a+b>=mod?mod:0);
}
inline int get_power(int a,int n)
{
	int res=1;
	while(n>0)
	{
		res=n&1?1ll*res*a%mod:res;
		a=1ll*a*a%mod;
		n>>=1;
	}
	return res;
}
int n,m;
inline int id(int x,int y)
{
	return (x-1)*(m<<1)+(y-1);
}
const int max_n=1e3+5;
const int max_m=1e3+5;
char str[max_m];
int Map[max_n<<1][max_m<<1];
const int max_tot=4e6+5;
int pow2[max_tot],pow_inv2[max_tot],Hash[max_n<<1][max_m<<1];
inline int get_Hash(int a,int b,int c,int d) // calculate the hash value of the matrix that the upper left corner is (a,b) and the lower right corner is (c,d)
{
	return (1ll*Hash[c][d]-Hash[a-1][d]-Hash[c][b-1]+Hash[a-1][b-1]+2*mod)*pow_inv2[id(a,b)]%mod;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",str+1);
		for(int j=1;j<=m;++j)
			Map[i][j]=Map[i+n][j]=Map[i][j+m]=Map[i+n][j+m]=(str[j]=='.');
	}
	pow2[0]=1;
	for(int i=1;i<=(n*m<<2);++i)
		pow2[i]=get_sum(pow2[i-1],pow2[i-1]);
	pow_inv2[n*m<<2]=get_power(pow2[n*m<<2],mod-2);
	for(int i=(n*m<<2)-1;i>=0;--i)
		pow_inv2[i]=get_sum(pow_inv2[i+1],pow_inv2[i+1]); 
	for(int i=1;i<=(n<<1);++i)	
		for(int j=1;j<=(m<<1);++j)
			Hash[i][j]=(1ll*Map[i][j]*pow2[id(i,j)]+Hash[i-1][j]+Hash[i][j-1]-Hash[i-1][j-1]+mod)%mod;
	int ans_x=1,ans_y=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			int L=1,R=n,res_x=n+1,res_y=m+1;
			while(L<=R)
			{
				int mid=(L+R)>>1;
				if(get_Hash(i,j,i+mid-1,j+m-1)!=get_Hash(ans_x,ans_y,ans_x+mid-1,ans_y+m-1))
					res_x=mid,R=mid-1;
				else
					L=mid+1;
			}
			if(res_x==n+1)
				continue;
			L=1,R=m;
			while(L<=R)
			{
				int mid=(L+R)>>1;
				if(get_Hash(i+res_x-1,j,i+res_x-1,j+mid-1)!=get_Hash(ans_x+res_x-1,ans_y,ans_x+res_x-1,ans_y+mid-1))
					res_y=mid,R=mid-1;
				else
					L=mid+1;
			}
			if(!Map[i+res_x-1][j+res_y-1])
				ans_x=i,ans_y=j;
		}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
			putchar(Map[ans_x+i-1][ans_y+j-1]?'.':'*');
		putchar('\n');
	}
	return 0;
}

官方 std

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 1010, MOD = 1e9 + 7, P = 2, Q = 3;

int pq_pow[2 * MAXN][2 * MAXN];
int h[2 * MAXN][2 * MAXN];

int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}
int sub(int a, int b) { return add(a, MOD - b); }
int mul(int a, int b) { return (ll)a * b % MOD; }

void precalc(const vector<string>& a) {
    for (int i = 0; i < 2 * MAXN; i++) {
        for (int j = 0; j < 2 * MAXN; j++) {
            if (i == 0 && j == 0) pq_pow[i][j] = 1;
            else if (i == 0) pq_pow[i][j] = mul(pq_pow[i][j - 1], Q);
            else pq_pow[i][j] = mul(pq_pow[i - 1][j], P);
        }
    }

    int n = a.size(), m = a[0].size();
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * m; j++) {
            int val = mul(a[i % n][j % m] == '.', pq_pow[i][j]);
            h[i + 1][j + 1] = sub(add(val,
                        add(h[i + 1][j], h[i][j + 1])),
                    h[i][j]);
        }
    }
}

int get_h(int x, int y, int dx, int dy) {
    return sub(add(h[x + dx][y + dy], h[x][y]),
            add(h[x][y + dy], h[x + dx][y]));
}

bool is_equal(int x1, int y1, int x2, int y2, int dx, int dy) {
    int val1 = mul(get_h(x1, y1, dx, dy), pq_pow[x2][y2]);
    int val2 = mul(get_h(x2, y2, dx, dy), pq_pow[x1][y1]);
    return val1 == val2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    precalc(a);

    int sol_x = 0, sol_y = 0;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            int lo_dx = 0, hi_dx = n;
            while (lo_dx + 1 < hi_dx) {
                int dx = (lo_dx + hi_dx) / 2;
                if (is_equal(sol_x, sol_y, x, y, dx, m)) lo_dx = dx;
                else hi_dx = dx;
            }
            int dx = lo_dx;

            int lo_dy = 0, hi_dy = m;
            while (lo_dy + 1 < hi_dy) {
                int dy = (lo_dy + hi_dy) / 2;
                if (is_equal(sol_x + dx, sol_y, x + dx, y, 1, dy)) lo_dy = dy;
                else hi_dy = dy;
            }
            int dy = lo_dy;


            if (a[(x + dx) % n][(y + dy) % m] <
                a[(sol_x + dx) % n][(sol_y + dy) % m]) {
                sol_x = x;
                sol_y = y;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << a[(sol_x + i) % n][(sol_y + j) % m];
        cout << '\n';
    }

    return 0;
}