题目见：https://acm.ecnu.edu.cn/contest/231/problem/B/
卡在第二个点和第十二个点上无数次。
和226打电话，226建议双哈希，然后一发过了。。。。（这是226大佬的力量啊）
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 1005 const int mod[2]={19260817,19190504},mul[2]={29,11}; int hash[2][maxn],ha[2][maxn][10][10],flag[10]; int q[5][10],top[5],n,m,K,ans,a[10],tail,now[2]; char s[maxn]; using namespace std; struct in { int q[2]; }b[maxn]; bool cmp(in x,in y) { if (x.q[0]==y.q[0]) return x.q[1]<y.q[1]; return x.q[0]<y.q[0]; } void dfs(int x,int last) { int i; if (x>tail) { int j,k,t,tot,now=0,cnt; for (i=0;i<last;i++) { if (top[i]==1) return; if (top[i]>1) now+=top[i]-1; } if (now>K) return; //printf("%d ",now); for (i=1;i<=n;i++) for (t=0;t<=1;t++) b[i].q[t]=hash[t][i]; for (i=0;i<last;i++) for (k=2;k<=top[i];k++) for (j=1;j<=n;j++) for (t=0;t<=1;t++) b[j].q[t]=(b[j].q[t]-ha[t][j][q[i][k]][q[i][k]]+ha[t][j][q[i][k]][q[i][1]]+mod[t])%mod[t]; cnt=0;tot=1; sort(b+1,b+n+1,cmp); for (j=2;j<=n;j++) if (b[j].q[0]==b[j-1].q[0] && b[j].q[1]==b[j-1].q[1]) tot++; else { cnt+=tot*(tot-1)/2; tot=1; } cnt+=tot*(tot-1)/2; //printf("%d %d %d ",cnt,tot,x); if (cnt>ans) ans=cnt; return; } for (i=0;i<last;i++) { q[i][++top[i]]=a[x]; dfs(x+1,last); top[i]--; } if (last<4) { q[last][++top[last]]=a[x]; dfs(x+1,last+1); top[last]--; } dfs(x+1,last); return; } int main() { int now[2],i,j,k,t; scanf("%d%d%d",&n,&m,&K); for (i=1;i<=n;i++) { scanf("%s",s); now[0]=1;now[1]=1; for (j=0;j<m;j++) for (t=0;t<=1;t++) { for (k=0;k<8;k++) ha[t][i][s[j]-'a'][k]=(ha[t][i][s[j]-'a'][k]+('a'+k)*now[t]%mod[t])%mod[t]; hash[t][i]=(hash[t][i]+s[j]*now[t]%mod[t])%mod[t]; now[t]=now[t]*mul[t]%mod[t]; flag[s[j]-'a']=1; } } for (i=0;i<8;i++) if (flag[i]) a[++tail]=i; if (K>=tail-1) { printf("%d",n*(n-1)/2); return 0; } dfs(1,0); printf("%d",ans); return 0; }