hash函数，通常用于将字符串映射到整数的函数，一般将值域映射到1e9或1e18以内，尽量避免哈希冲突并且便于比较。
选取哈希进制base和模数mod，尽量选取质数，对于一个字符串s的哈希值就是f(s)=sum(i=1->l)(s[i]*base^(l-i)%mod).
比较两个字符串相等时，可以直接比较哈希值，但是对于多模哈希而言，需要都相等才行。
常用的进制数：
由1,2,3组成的三位数，如131,233,313.
或者四位数，如1321,1231.
常用的模数：
998244353,1e9+7,993244853,19260817,100000000000000001,100000000000000003,100000000000000013.
有模哈希，有几率超时。
inline int makehash(string s){
int re=0,n=s.size();
for(int i=0;i<n;i++)re=(re*base+s[i])%mod;
return re;
}
无模哈希，有几率被卡。
inline ull makehash(string s){
ull re=0,n=s.size();
for(int i=0;i<n;i++)re=re*base+s[i];
return re;
}
双模哈希，有几率超时，进制数可以相同，但是模数必须不同。
inline pair<int,int>makehash(string s){
int n=s.size(),a=0,b=0;
for(int i=0;i<n;i++)a=(a*base[0]+s[i])%mod[0],b=(b*base[1]+s[i])%mod[1];
return {a,b};
}
对于询问子串的哈希值，需要提前把整个串的哈希值存下来，并且预处理进制的每次幂，f(s[l...r])=s[l]base(r-l)+s[l+1]*base(r-l-1)+...+s[r-1]base+s[r]=f(r)-f(l-1)*base^(r-l+1).
有模哈希。
inline void prework(){
pre[0]=1;
for(int i=1;i<=n;i++)pre[i]=(pre[i-1]*base)%mod;
}
inline int gethash(int l,int r){
return (hs[r]-hs[l-1]*pre[r-l+1]%mod+mod)%mod;
}
无模哈希。
inline void prework(){
pre[0]=1;
for(int i=1;i<=n;i++)pre[i]=pre[i-1]*base;
}
inline ull gethash(int l,int r){
return hs[r]-hs[l-1]*pre[r-l+1];
}
删掉第k位，求剩下的串的哈希值。首先计算出原完整串的哈希值，之后减去s[1...k]子串的哈希值，即hs[k]pw[n-k]，在将s[1...k-1]向右移动一格，再加上其哈希值hs[k-1]pw[n-k].
x=hs[n]-hs[k]*pw[n-k]+hs[k-1]*pw[n-k];
二维哈希判断矩阵相等。去两个不同的base，先对每行进行哈希，再对每行的哈希值进行纵向哈希，查询时与二维前缀和类似。
求一个矩阵中上下对称且左右对称的正方形的个数。
const int N=1e3+3,base[]={233,313};
int n,m,ans,a[N<<1][N<<1];
ull pw[2][N<<1],sum[N<<1][N<<1];
inline ull gethash(int x,int y,int a,int b){
return sum[a][b]-sum[x-1][b]*pw[1][a-x+1]-sum[a][y-1]*pw[0][b-y+1]+sum[x-1][y-1]*pw[0][b-y+1]*pw[1][a-x+1];
}
inline bool check(int x,int y,int a,int b){
return gethash(x,y,a,b)==gethash((n<<1)-a+1,y,(n<<1)-x+1,b)/*判断矩形是否左右对称*/&&gethash(x,y,a,b)==gethash(x,(m<<1)-b+1,a,(m<<1)-y+1)/*判断举行是否上下对称*/;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i+n][j]=a[n-i+1][j],a[i][j+m]=a[i][m-j+1];/*将矩形向右、向下进行翻转*/
pw[0][0]=pw[1][0]=1;
for(int i=1;i<=min(n,m)<<1;i++)pw[0][i]=pw[0][i-1]*base[0],pw[1][i]=pw[1][i-1]*base[1];/*预处理横纵坐标的base，pw[0]对应y轴，pw[1]对应x轴*/
for(int i=1;i<=n<<1;i++)for(int j=1;j<=m<<1;j++)sum[i][j]=sum[i][j-1]*base[0]+a[i][j];/*纵向处理y轴哈希*/
for(int i=1;i<=n<<1;i++)for(int j=1;j<=m<<1;j++)sum[i][j]+=sum[i-1][j]*base[1];/*将y轴哈希横向再次进行哈希*/
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int l=1,r=min(n,m),re=0;
while(l<=r){/*枚举奇数回文矩阵对称中心点*/
int mid=l+r>>1;
if(i-mid+1>=1&&j-mid+1>=1&&i+mid-1<=n&&j+mid-1<=m&&check(i-mid+1,j-mid+1,i+mid-1,j+mid-1)==true)l=mid+1,re=mid;
else r=mid-1;
}
ans+=re;
l=re=0,r=min(n,m);
while(l<=r){/*枚举偶数回文矩阵你对称点左下角*/
int mid=l+r>>1;
if(i-mid+1>=1&&j-mid+1>=1&&i+mid<=n&&j+mid<=m&&check(i-mid+1,j-mid+1,i+mid,j+mid)==true)l=mid+1,re=mid;
else r=mid-1;
}
ans+=re;
}
}
cout<<ans;
return 0;
}
树同构问题，利用哈希判断一些有根树或者无根树是否同构。
设计哈希函数，f(x)表示以1为根时x对应子树的哈希值，f[x]=1+sum(y属于son[x])(f[y]*prime[sz[y]])。
注意判断同构前先判断树的大小是否相等，不等时也有可能两棵树的f[1]相等。
之后利用换根dp，计算g[x]表示以x为根是全树的哈希值，g[x]=f[x]+(prime[sz[1]-sz[x])(g[fa[x]]-f[x]prime[sz[x])，也就是自己子树的哈希值，加上自己父亲为根时全树的哈希值再删掉自己的贡献再乘上子树外的sz成为子树外的哈希值。
一般判断用f[]即可，但是g[]更加不容易出现问题。
struct Tree{
int fa[N],sz[N],f[N],g[N];
vector<int>v[N];
inline void add(int x,int y){v[x].emplace_back(y);}
void dfs(int x,int fat){
fa[x]=fat;
sz[x]=f[x]=1;
for(auto y:v[x]){
if(y==fat)continue;
dfs(y,x);
sz[x]+=sz[y];
f[x]+=f[y]*prime[sz[y]];
}
}
void dfs(int x){
g[x]=f[x]+prime[sz[1]-sz[x]]*(g[fa[x]]-f[x]*prime[sz[x]]);
for(auto y:v[x])if(y!=fa[x])dfs(y);
}
}t[N];
for(int i=1;i<=m;i++){
mp.clear();
for(int x=1;x<=t[i].sz[1];x++)mp.insert({t[i].g[x],1});
bool flag=false;
for(int j=1;j<=m;j++){
if(t[i].sz[1]!=t[j].sz[1])continue;
for(int x=1;x<=t[j].sz[1];x++)if(mp.find(t[j].g[x])!=mp.end()){
flag=true;
cout<<j<<'\n';
break;
}
if(flag==true)break;
}
}
随机数哈希。
为每个点赋随机权值，常用的有sum Hash和xor Hash，即通过判断哈希和或者哈希异或和来判断是否相等。
一张有向图，每条边都有激活与失活两种状态，有四种操作，激活某条边，激活以某个点为终点的每条边，失活某条边，失活以某个点为终点的每条边，每次询问只考虑激活的边，是否满足每个点出度均为1，且每个点都能够走到一个环上。n个点n条边，所以每个点都能都能走到环上，根本不用判环，然而我赛时根本没有想到，于是就连暴力都没有打，整张图就是一个基环树森林。显然入度比出度好维护，维护入度可以做到O(1)，为每个点x赋一个随机权值w[x]，从x出发的每条边的边权都是w[x]，再记录每个点为终点得到的权值和，即in[y]=sum(w[x])[(x->y)有边],每个点出度均为1时有极大概率时sum(w[x])==sum(in[x]).
Code:
signed main(){
srand(time(0));
cin>>n>>m;
for(int i=1;i<=n;i++)w[i]=rand(),sum+=w[i];
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
in[b]+=w[a];
g[b]=in[b];
now+=w[a];
}
cin>>q;
while(q--){
int op,x,y;
cin>>op>>x;
if(op&1)cin>>y;
switch(op){
case 1:now-=w[x];in[y]-=w[x];break;
case 2:now-=in[x];in[x]=0;break;
case 3:now+=w[x];in[y]+=w[x];break;
case 4:now+=g[x]-in[x];in[x]=g[x];break;
}
cout<<(sum==now?"YES\n":"NO\n");
}
return 0;
}
哈希表是一种通过哈希函数将元素一一映射的数据结构，分为闭散列和开散列两种。
闭散列，也叫开放定址法，是当元素出现冲突时，向后探查直到有空位，常见的有线性探查和二次探查两种。
线性探查即为挨个位置向后探查，二次探查为每次以平方的距离向后探查。
template<class K,class V>
class HashTable{
enum State{/*枚举状态*/
EXIST,/*存在*/
EMPTY,/*空*/
DELETE/*被删除*/
};
struct Data{
pair<K,V>data;
State state=EMPTY;
};
vector<Data>table;
size_t n=0;
template<class T>inline size_t hash(const T&x){/*整形哈希值*/
const size_t mod=table.size();
return (x%mod+mod)%mod;
}
template<class T,class t>inline size_t hash(const pair<T,t>&x){
const size_t mod=table.size();
return (hash(x.first)+hash(x.second))%mod;
}
inline size_t hash(const string&s){/*字符串哈希值*/
const size_t mod=table.size();
size_t re=0,n=s.size();
for(int i=0;i<n;i++)re=(re*131+s[i])%mod;
return re;
}
inline void resize(){/*进行扩容*/
if(n<=0.7*table.size())return;/*负载因子尚未达到扩容标准*/
HashTable<K,V>ht;
ht.table.resize(2*table.size());/*2倍空间*/
for(auto&x:table)if(x.state==EXIST)ht.insert(x.data);/*旧表中存在的元素依次插入*/
table.swap(ht.table);/*交换两个表*/
}
public:
inline HashTable(size_t capacity=10):table(capacity),n(0){}/*初始化最大容量*/
inline size_t size(){
return n;
}
inline bool empty(){
return n==0;
}
inline Data*find(const K&key){
size_t idx=hash(key);/*获取哈希值*/
while(table[idx].state!=EMPTY){/*当不为空时一直线性探测*/
if(table[idx].data.first==key&&table[idx].state==EXIST)return &table[idx];/*找到对应元素并且该元素存在则返回索引*/
if(++idx==table.size())idx=0;/*向后探测*/
}
return nullptr;/*未找到该元素*/
}
inline Data*insert(const pair<K,V>&x){
Data*re=find(x.first);
if(re!=nullptr)return re;/*已经存在的元素直接返回*/
resize();/*判断扩容*/
size_t idx=hash(x.first);
while(table[idx].state==EXIST)/*当前位置有元素存在则一直向后线性探测*/if(++idx==table.size())idx=0;
table[idx]={x,EXIST};/*插入元素*/
n++;/*修改元素数量*/
return &table[idx];
}
inline Data*insert(const K&key){
Data*re=find(key);
if(re!=nullptr)return re;
resize();
size_t idx=hash(key);
while(table[idx].state==EXIST)if(++idx==table.size())idx=0;
table[idx].data.first=key;
table[idx].state=EXIST;
n++;
return &table[idx];
}
inline V&operator[](const K&key){
Data*re=insert(key);/*无论是否有，先插入该元素*/
return re->data.second;
}
inline bool erase(const K&key){
Data*re=find(key);
if(re!=nullptr){/*当前元素存在*/
re->state=DELETE;/*更新状态为删除*/
--n;/*修改元素数量*/
return true;/*删除成功*/
}
return false;/*删除失败*/
}
};
开散列，也叫哈希桶，链地址法，具有相同哈希值的元素归入到同一个桶中，各链表的头结点存储在哈希表中。
template<class K,class V>
class HashTable{
struct Data{
pair<K,V>data;
Data*next;
inline Data(const pair<K,V>&x):data(x),next(nullptr){}
inline Data(const K&key):next(nullptr){data.first=key;}
};
vector<Data*>table;
size_t n=0;
template<class T>inline size_t hash(const T&x,const size_t mod){/*获取整数哈希值*/
return (x%mod+mod)%mod;
}
template<class T,class t>inline size_t hash(const pair<T,t>&x,const size_t mod){
return (hash(x.first,mod)+hash(x.second,mod))%mod;
}
inline size_t hash(const string&s,const size_t mod){/*字符串哈希值*/
size_t re=0,n=s.size();
for(int i=0;i<n;i++)re=(re*131+s[i])%mod;
return re;
}
inline void resize(){/*进行扩容*/
if(n!=table.size())return;/*当元素个数不到最大容量时不扩容*/
vector<Data*>ht;
ht.resize(table.size()*2);/*2倍内存*/
for(auto p:table){/*对每个元素插入*/
while(p!=nullptr){
Data*next=p->next;/*记录下一个的指针*/
size_t idx=hash(p->data.first,ht.size());/*获取哈希值*/
p->next=ht[idx];/*当前元素插入到表头前面*/
ht[idx]=p;/*表头指向当前元素*/
p=next;/*跳到下一个*/
}
}
table.swap(ht);/*交换两张表*/
}
public:
inline HashTable(size_t capacity=10):table(capacity,nullptr),n(0){}/*初始化最大容量*/
inline Data*insert(const pair<K,V>&x){
Data*re=find(x.first);
if(re!=nullptr)return re;/*已经存在元素则直接返回*/
resize();/*判断扩容*/
size_t idx=hash(x.first,table.size());
re=new Data(x);/*创建新的元素*/
re->next=table[idx];/*插入到表头之前*/
table[idx]=re;/*表头指向该元素*/
n++;/*修改元素数量*/
return re;
}
inline Data*insert(const K&key){
Data*re=find(key);
if(re!=nullptr)return re;
resize();
size_t idx=hash(key,table.size());
re=new Data(key);
re->next=table[idx];
table[idx]=re;
n++;
return re;
}
inline V&operator[](const K&key){
Data*re=insert(key);/*无论是否有都插入该元素*/
return re->data.second;
}
inline Data*find(const K&key){
size_t idx=hash(key,table.size());
Data*p=table[idx];/*获取索引*/
while(p!=nullptr){
if(p->data.first==key)return p;/*找到对应元素则返回指针*/
p=p->next;/*跳到下一个*/
}
return nullptr;/*未找到该元素*/
}
inline Data*erase(const K&key){
size_t idx=hash(key,table.size());
Data*p=table[idx],*pre=nullptr,*re=nullptr;
while(p!=nullptr){
if(p->data.first==key){/*找到对应元素*/
if(pre==nullptr)table[idx]=p->next;/*删除的是第一个元素，将表头指向当前的下一个*/
else pre->next=p->next;/*否则将前一个的下一个指向当前的下一个*/
re=p->next;/*下一个元素*/
delete p;/*释放指针*/
n--;/*修改元素数量*/
return re;/*返回删除元素的下一个*/
}
pre=p;/*修改前驱指针*/
p=p->next;/*跳到下一个*/
}
return nullptr;
}
};
将n个数分为若干个长为k的串，长度不足k则丢弃，求使得不同的串最多的k值及串的个数，串可翻转。枚举k和每个串，假设判断为O(1)，由调和级数可得，时间复杂度为O(N*log2(N))，正反向都处理出哈希数组，比较时判断该哈希值是否在当前枚举的长度k中出现过，没有出现过则cnt++，并将该串的正反两个哈希值标记为k.
constexpr int N=1e6+6,base=19260817,mod=1e7+7;
int pre[N],suc[N],pw[N],a[N],ans[N],ma,h[mod];
for(int i=1;i<=n;i++){
cin>>a[i];
pw[i]=pw[i-1]*base%mod;
pre[i]=(pre[i-1]*base%mod+a[i])%mod;
}
for(int i=n;i;i--)suc[i]=(suc[i+1]*base%mod+a[i])%mod;
for(int k=1;n/k>=ma;k++){
int cnt=0;
for(int i=k;i<=n;i+=k){
int p=(pre[i]-pre[i-k]*pw[k]%mod+mod)%mod;
if(h[p]==k)continue;
cnt++;
h[p]=k;
p=(suc[i-k+1]-suc[i+1]*pw[k]%mod+mod)%mod;
h[p]=k;
}
if(cnt>ma)ma=cnt,ans[ans[0]=1]=k;
else if(cnt==ma)ans[++ans[0]]=k;
}
对于一个串，询问区间最小循环节长度。线性筛找出每个数的最小质因数，若x是循环节，那么x肯定是len的约数，且x的倍数也是循环节，若s[l...r-len]=s[l+len,r]，则len为[l,r]内的一个循环节长度。每次询问将len质因数分解，枚举循环次数，如果可以整除且整除后可以是循环节则整除。
while(q--){
int l,r,len,top=0;
cin>>l>>r;
len=r-l+1;
if(gethash(l+1,r)==gethash(l,r-1)){
cout<<1<<'\n';
continue;
}
while(len>1)stk[++top]=mi[len],len/=mi[len];
len=r-l+1;
for(int i=1;i<=top;i++){
int x=len/stk[i];
if(gethash(l+x,r)==gethash(l,r-x))len=x;
}
cout<<len<<'\n';
}
对于串s和t，若s的一个后缀移到开头后和t相等，则s和t循环同构，求给出串的最长l前缀和l后缀，使得l前缀和l后缀循环同构。将s拆分成abcba形式，也就是对于每一个长i且小于n/2的border，求s[i+1,n-i]的最长border为f[i]，i+f[i]的max即为答案。
for(int i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1])j=nxt[j];
if(s[i]==s[j+1])j++;
nxt[i]=j;
}
pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*base%mod,hs[i]=(hs[i-1]*base%mod+s[i])%mod;
for(int i=n>>1;i;i--){
f[i]=f[i+1]+2;
while(f[i]&&i+f[i]>n>>1||gethash(i+1,i+f[i])!=gethash(n-i-f[i]+1,n-i))f[i]--;
}
int ans=0;
for(int i=nxt[n];i;i=nxt[i])if(i<=n>>1)ans=max(ans,i+f[i]);