BZOJ2462: [BeiJing2011]矩阵模板 二维Hash

这题我们只需要把所有\(A*B\)的子矩阵的hash值存下来，然后\(O(1)\)回答每次询问即可。

那么关键就是如何确定一个矩阵的hash值。

考虑对于一个长度为\(n\),下标范围为\([0,n-1]\)的字符串，我们对于\(seed,mod\),随后定义字符串的一个后缀的函数:

\(f_i=(seed*f_{i+1}+s_i)\%mod\)

特别的\(f_{n-1}=s_{n-1}\)

那么我们若想取得这个字符串的子串\([l,r]\)的hash值，就可以用\((f_l-f_{r+1}*seed^{r-l+1})\%mod\)就行了。

接下来只需要类似一维的形式将hash拓展到二维形式即可。

下面是代码。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef unsigned long long LLU;
static const int Base1=23333;
static const int Base2=233;
 
static const int SetMod=7233333;
struct HashSet{
    bool vis[SetMod];
    inline void Insert(LLU _v){
        vis[_v%SetMod]=1;
    }
    int operator[](const LLU _v){
        return vis[_v%SetMod]==1;
    }
}S;
 
#define N 1010
LLU h[N][N],Pow1[N],Pow2[N];
int d[N][N];
LLU f(int x,int L,int R){return h[x][L]-h[x][R+1]*Pow1[R-L+1];}
LLU g(int x,int y,int L,int R){return f(x,L,R)-f(y+1,L,R)*Pow2[y-x+1];}
 
int src[N][N];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    int n,m,A,B;scanf("%d%d%d%d",&n,&m,&A,&B);
    register int i,j;
    for(Pow1[0]=1,i=1;i<=100;++i)Pow1[i]=Pow1[i-1]*Base1;
    for(Pow2[0]=1,i=1;i<=100;++i)Pow2[i]=Pow2[i-1]*Base2;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%1d",&d[i][j]);
    for(i=n;i>=1;--i){
        for(j=m;j>=1;--j)h[i][j]=h[i][j+1]*Base1+d[i][j];
        for(j=1;j<=m;++j)h[i][j]=h[i+1][j]*Base2+h[i][j];
    }
     
    for(i=A;i<=n;++i)for(j=B;j<=m;++j)S.Insert(g(i-A+1,i,j-B+1,j));
 
    int Q;cin>>Q;
    while(Q--){
        for(i=1;i<=A;++i)for(j=1;j<=B;++j)scanf("%1d",&src[i][j]);
        LLU res(0),now,mi1,mi2;
        for(mi2=i=1;i<=A;++i,mi2=mi2*Base2){
            for(now=0,mi1=1,j=1;j<=B;++j,mi1=mi1*Base1)now=now+src[i][j]*mi1;
            res=res+mi2*now;
        }
        printf("%d\n",S[res]);
    }return 0;
}


还有下面一份能AC的(伪)代码，我就剧透一下.

for(int i=1;i<=10;++i)puts("1");

只能说数据逆天。。。