Description
- 给定一个仅含有大写字母的n*m（n,m<=110）的矩阵，求不同的矩阵个数。
Solution
- 考虑枚举按照宽度将矩阵分类，分别统计。
- 将每一行的每个位置开头，且长度该宽度的字串压一个编号，同一列的该宽度字串上下拼接即可形成任意一个该宽度下的矩阵。
- 将每一列的编号排列成一个字符串，设为Si
- 将所有列的S排列成：S1#S2#S3#…Sk
- 我们只需要用后缀自动机求出这个大的字符串（字符域取决于你的编号的多少）中的不同字串个数就好了。
Q&A
- 为什么要将每一列的S连起来而不分开求？因为这个宽度下的矩阵是一类的，有重复的情况要计算到。
- 怎么压编号？也许你可以哈希（双哈希，用单哈希会爆），但我用的是trie，空间复杂度就很大了。
- 有#的后缀自动机怎么求其中不同字串个数(‘S1#’ = 'S2#'算重）？用自动机的边构成的DAG做DP时，判断一下是不是#，如果是的话就不要转移，这样就能保证计算到的字符串没有#
PS
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#define maxn 111
#define maxm 30000
#define maxp 1000005
#define ll long long
using namespace std;
int n,m,i,j,k,l,tot,a[maxn][maxn],nm[maxn][maxn][maxn];
int x,y,tr[maxp][27],sz,bz[maxp];
int du[maxm],t,w,d[maxm],f[maxm];
char ch;
ll ans;
int rt=1,las,num,fa[maxm],len[maxm];
map<int,int> to[maxm];
map<int,int>::iterator it;
void add(int c){
int p=las,np=las=++num; to[np].clear();
len[np]=len[p]+1;
for(;p&&!to[p][c];p=fa[p])
to[p][c]=np;
if (!p) fa[np]=rt; else {
int q=to[p][c];
if (len[q]==len[p]+1) fa[np]=q; else {
int nq=++num; to[nq].clear();
len[nq]=len[p]+1;
fa[nq]=fa[q],fa[q]=fa[np]=nq;
to[nq]=to[q];
for(;p&&to[p][c]==q;p=fa[p]) to[p][c]=nq;
}
}
}
void tropu(){
for(i=1;i<=num;i++)
for(it=to[i].begin();it!=to[i].end();it++)
du[it->second]++;
memset(f,0,sizeof(f));
t=0,w=1,d[1]=1,f[1]=1;
while (t<w){
x=d[++t];
for(it=to[x].begin();it!=to[x].end();it++) {
y=it->second;
du[y]--;
if (!du[y]) d[++w]=y;
if (it->first) f[y]+=f[x];
}
}
for(i=2;i<=num;i++) ans+=f[i];
}
int main(){
freopen("matrix9.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) for(j=1;j<=m;j++) {
for(ch=getchar();ch<'A'||ch>'Z';ch=getchar());
a[i][j]=ch-'A'+1;
}
tot=1;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) {
x=1;
for(k=j;k<=m;k++) {
if (!tr[x][a[i][k]]) tr[x][a[i][k]]=++tot;
x=tr[x][a[i][k]];
nm[i][j][k]=x;
}
}
}
for(l=0;l<m;l++) {
sz=0,num=1,las=rt; to[rt].clear();
for(j=1;j+l<=m;j++) {
for(i=1;i<=n;i++) {
if (!bz[nm[i][j][j+l]])
bz[nm[i][j][j+l]]=++sz;
add(bz[nm[i][j][j+l]]);
}
add(0);
}
tropu();
}
printf("%lld",ans);
}