펭귄 QQhash

하하 20s 카드 오버~\(≥;≤)/~
근데 쌍해시를 썼어요...천천히 달리는 것도 정상이다.
sb문제.다른 누구를 직접 매거하고 나머지hash가 동일한지 판단하면 됩니다.구체적으로 빨리 배열하거나 해시표로 답을 통계할 수 있다.
AC 코드는 다음과 같습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#define mod1 1000000009
#define mod2 900000083
#define ll long long
#define N 30005
#define M 205
using namespace std;

int n,m,ans,pw1[M],pw2[M],sv1[N][M],sv2[N][M]; char ch[M];
struct hsh_node{
	int cnt,tot,h[N],fst[2010527],px[N],py[N],pu[N],pv[N],len[N],nxt[N];
	void clr(){
		while (cnt) fst[h[cnt--]]=0; tot=0;
	}
	void ins(int x,int y,int u,int v){
		int z=((ll)x*1000003+y)%2010527,w=((ll)u*2000003+v)%2010527,p;
		z=(z*103+w)%2010527;
		for (p=fst[z]; p; p=nxt[p])
			if (px[p]==x && py[p]==y && pu[p]==u && pv[p]==v){
				ans+=len[p]; len[p]++;
				return;
			}
		if (!fst[z]) h[++cnt]=z;
		px[++tot]=x; py[tot]=y; pu[tot]=u; pv[tot]=v;
		len[tot]=1; nxt[tot]=fst[z]; fst[z]=tot;
	}
}hsh;
int get1(int x,int y,int z){ return (sv1[x][y]-(ll)sv1[x][y+z]*pw1[z]%mod1+mod1)%mod1; }
int get2(int x,int y,int z){ return (sv2[x][y]-(ll)sv2[x][y+z]*pw2[z]%mod2+mod2)%mod2; }
int main(){
	scanf("%d%d",&n,&m); int i,j; scanf("%d",&i);
	pw1[0]=pw2[0]=1;
	for (i=1; i<=m; i++){
		pw1[i]=(ll)pw1[i-1]*223%mod1; pw2[i]=(ll)pw2[i-1]*233%mod2;
	}
	for (i=1; i<=n; i++){
		scanf("%s",ch+1);
		for (j=m; j; j--){
			sv1[i][j]=((ll)sv1[i][j+1]*223+ch[j])%mod1;
			sv2[i][j]=((ll)sv2[i][j+1]*233+ch[j])%mod2;
		}
	}
	for (i=1; i<=m; i++){
		hsh.clr();
		for (j=1; j<=n; j++)
			hsh.ins(get1(j,1,i-1),get2(j,1,i-1),get1(j,i+1,m-i),get2(j,i+1,m-i));
	}
	printf("%d
",ans);
	return 0;
}

by lych
2016.5.26