暴力枚举不同的一位即可。。
主要是常数问题
1.统计答案时用sort速度快于用tr1/unordered_map,后者又快于map
(tr1/unordered_map完全达不到理论复杂度上的O(1)一次操作)(虽然复杂度一样,sort后统计比map要快得多)
2.幸好没卡自然溢出...双模hash直接T飞
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Hash
{
typedef ull Hdata;
#define N 1000000
const int X=;
Hdata pwx[N+];
void init()
{
pwx[]=;
for(int i=;i<=N;i++) pwx[i]=pwx[i-]*X;
}
struct H
{
Hdata h;int sz;
H():h(),sz(){}
H(const Hdata &a,int b):h(a),sz(b){}
};
H operator+(const H &a,const H &b)
{
H ans;ans.sz=a.sz+b.sz;
ans.h=a.h+b.h*pwx[a.sz];
return ans;
}
bool operator==(const H &a,const H &b)
{
return a.sz==b.sz&&a.h==b.h;
}
}
using Hash::Hdata;
using Hash::H;
using Hash::X;
using Hash::pwx; int n,l,s;ll ans;
struct S
{
Hdata hs[];
S& operator=(const char *s)
{
for(int i=;i<=l;i++)
{
hs[i]=hs[i-]*X+s[i];
}
return *this;
}
H gett(int l,int r)
{
if(l>r) return H();
return H(hs[r]-hs[l-]*pwx[r-l+],r-l+);
}
}ss[];
char tmp[];
Hdata tta[];
int main()
{
int i,j,ttt,tt2;
Hash::init();
scanf("%d%d%d",&n,&l,&s);
for(i=;i<=n;i++)
{
scanf("%s",tmp+);
ss[i]=tmp;
}
for(j=;j<=l;j++)
{
ttt=;
for(i=;i<=n;i++)
tta[++ttt]=(ss[i].gett(,j-)+ss[i].gett(j+,l)).h;
sort(tta+,tta+ttt+);tt2=;
for(i=;i<=ttt;i++)
{
tt2++;
if(i==ttt||tta[i+]!=tta[i])
{
//printf("%d %d\n",j,tt2);
ans+=tt2*(tt2-)/;
tt2=;
}
}
}
printf("%lld",ans);
return ;
}