4
19
2016
0

[BZOJ1085] [SCOI2005]骑士精神

双向BFS

怎么写着写着就5kb+了呢……其他人为什么跑得那么快……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int Smod=9973;
const pair<int,int> tab[]={make_pair(-1,-2),make_pair(-2,-1),make_pair(-1,2),make_pair(-2,1),make_pair(1,-2),make_pair(2,-1),make_pair(1,2),make_pair(2,1)};
const long long Lmod1=233333333333333ll,Lmod2=666666666666667ll;

int T,hn1,hn2,mat[10][10],h1[10005],h2[10005];
char mt[10][10];

struct Hash{
int next,step;
long long L1,L2;
}ha1[1000005],ha2[1000005];

void AddHash1(int s,long long l1,long long l2,int step){
ha1[++hn1].L1=l1;
ha1[hn1].L2=l2;
ha1[hn1].step=step;
ha1[hn1].next=h1[s];
h1[s]=hn1;
}

int FindHash1(int s,long long l1,long long l2){
for(int i=h1[s];i;i=ha1[i].next){
	if(ha1[i].L1==l1 && ha1[i].L2==l2)return i;
}
return 0;
}

void AddHash2(int s,long long l1,long long l2,int step){
ha2[++hn2].L1=l1;
ha2[hn2].L2=l2;
ha2[hn2].step=step;
ha2[hn2].next=h2[s];
h2[s]=hn2;
}

int FindHash2(int s,long long l1,long long l2){
for(int i=h2[s];i;i=ha2[i].next){
	if(ha2[i].L1==l1 && ha2[i].L2==l2)return i;
}
return 0;
}

struct Matrix{
int mt[6][6],now;
friend bool operator==(Matrix A,Matrix B){
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++)if(A.mt[i][j]!=B.mt[i][j])return 0;
}
return 1;
}
}Template;

pair<int,pair<long long,long long> > GetHash(Matrix M){
int s=0;
long long l1=0,l2=0;
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++){
		s=(s*127+M.mt[i][j])%Smod;
		l1=(l1*233+M.mt[i][j])%Lmod1;
		l2=(l2*667+M.mt[i][j])%Lmod2;
	}
}
return make_pair(s,make_pair(l1,l2));
}

queue<Matrix> Q1,Q2;

void OutMatrix(Matrix M){
puts("This is Mt:");
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++){
		printf("%d",M.mt[i][j]);
	}
	putchar('\n');
}
puts("-------------");
}

void BFS(int mode,int st){
if(st>8){puts("-1");return;}
if(mode){
	while(Q1.front().now==st){
		Matrix u=Q1.front();
		//OutMatrix(u);
		Q1.pop();
		int x,y;
		for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;}
		//printf("XY:%d %d\n",x,y);
		for(int i=0;i<8;i++){
			int px=x+tab[i].first,py=y+tab[i].second,tc;
			if(px<1 || py<1 || px>5 || py>5)continue;
			swap(u.mt[x][y],u.mt[px][py]);u.now++;
			pair<int,pair<long long,long long> >Pt=GetHash(u);
			tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second);
			if(tc){printf("%d\n",u.now+ha2[tc].step<=15?u.now+ha2[tc].step:-1);return;}
			tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second);
			if(!tc){AddHash1(Pt.first,Pt.second.first,Pt.second.second,u.now);Q1.push(u);}
			swap(u.mt[x][y],u.mt[px][py]);u.now--;
		}
	}
    BFS(mode^1,st);
    return;
}
else {
	while(Q2.front().now==st){
		Matrix u=Q2.front();
		//OutMatrix(u);
		Q2.pop();
		int x,y;
		for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;}
		//printf("XY:%d %d\n",x,y);
		for(int i=0;i<8;i++){
			int px=x+tab[i].first,py=y+tab[i].second,tc;
			if(px<1 || py<1 || px>5 || py>5)continue;
			swap(u.mt[x][y],u.mt[px][py]);u.now++;
			pair<int,pair<long long,long long> >Pt=GetHash(u);
			tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second);
			if(tc){printf("%d\n",u.now+ha1[tc].step<=15?u.now+ha1[tc].step:-1);return;}
			tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second);
			if(!tc){AddHash2(Pt.first,Pt.second.first,Pt.second.second,u.now);Q2.push(u);}
			swap(u.mt[x][y],u.mt[px][py]);u.now--;
		}
	}
    BFS(mode^1,st+1);
    return;
}
}

void MakeMt(Matrix &x){
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++){
		x.mt[i][j]=mat[i][j];
	}
}
x.now=0;
}

void Prepare(){
mat[1][1]=2;mat[1][2]=2;mat[1][3]=2;mat[1][4]=2;mat[1][5]=2;
mat[2][1]=1;mat[2][2]=2;mat[2][3]=2;mat[2][4]=2;mat[2][5]=2;
mat[3][1]=1;mat[3][2]=1;mat[3][3]=0;mat[3][4]=2;mat[3][5]=2;
mat[4][1]=1;mat[4][2]=1;mat[4][3]=1;mat[4][4]=1;mat[4][5]=2;
mat[5][1]=1;mat[5][2]=1;mat[5][3]=1;mat[5][4]=1;mat[5][5]=1;
}

void First(){
while(!Q1.empty())Q1.pop();
while(!Q2.empty())Q2.pop();
memset(h1,0,sizeof(h1));
memset(h2,0,sizeof(h2));
hn1=0;hn2=0;
}

int main(){
freopen("1085.in","r",stdin);
freopen("1085.out","w",stdout);
scanf("%d",&T);
Prepare();
MakeMt(Template);
while(T--){
	First();
	scanf("%s %s %s %s %s",mt[1]+1,mt[2]+1,mt[3]+1,mt[4]+1,mt[5]+1);
    for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(mt[i][j]=='0')mat[i][j]=1;
			else if(mt[i][j]=='1')mat[i][j]=2;
			else mat[i][j]=0;
		}
    }
    Matrix Tp;
    pair<int,pair<long long,long long> > Pr;
    MakeMt(Tp);
    if(Tp==Template){puts("0");continue;}
    Q1.push(Tp);
    Q2.push(Template);
    Pr=GetHash(Tp);
    AddHash1(Pr.first,Pr.second.first,Pr.second.second,0);
    Pr=GetHash(Template);
    AddHash2(Pr.first,Pr.second.first,Pr.second.second,0);
    BFS(1,0);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
19
2016
0

[BZOJ3218] a + b Problem

这是一个卡内存的悲伤故事

我把UOJ爆了一通才卡完内存,然后又发现在BZOJ上MLE了

然后又是乱卡一通,终于A掉了

题解(PoPoQQQ)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int INF=2100000000,N=900005;

int n,en,S,T,level[N],h[N],cur[N],his[5005],cnt,flow_cnt,ans;
queue<int> Q;

struct Edge{
int b,f,back,next;
}e[N];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
    for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(!e[i].f || level[v])continue;
		level[v]=level[u]+1;
		Q.push(v);
    }
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
    if(e[i].f && level[v]==level[u]+1 && (fl=DFS(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		f-=fl;
		if(f==0)return flow;
    }
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=flow_cnt;i++)cur[i]=h[i];ans+=DFS(S,2100000000);}
return ans;
}

struct SegTree{
int nl,nr,v,pos;
}tree[N];

void Newnode(int &rt,int lastrt){
rt=++cnt;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
tree[rt].pos=++flow_cnt;
}

void Update(int &rt,int lastrt,int l,int r,int pos,int val){
Newnode(rt,lastrt);
int mid=l+r>>1;
AddEdge(val,tree[rt].pos,INF);
if(lastrt)AddEdge(tree[lastrt].pos,tree[rt].pos,INF);
if(l==r)return;
if(pos<=mid)Update(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val);
if(pos>mid)Update(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val);
}

void Query(int rt,int l,int r,int x,int y,int point){
if(!rt)return;
if(x<=l && r<=y){AddEdge(tree[rt].pos,point,INF);return;}
int mid=l+r>>1;
if(x<=mid)Query(tree[rt].nl,l,mid,x,y,point);
if(y>mid)Query(tree[rt].nr,mid+1,r,x,y,point);
}

int main(){
freopen("3218.in","r",stdin);
freopen("3218.out","w",stdout);
scanf("%d",&n);
S=n*2+1;T=n*2+2;flow_cnt=n*2+2;
for(int i=1;i<=n;i++){
	int a,b,w,l,r,p;
    scanf("%d %d %d %d %d %d",&a,&b,&w,&l,&r,&p);
    ans+=b+w;
    AddEdge(S,i+n,w);AddEdge(i+n,T,b);
    AddEdge(i,i+n,p);
    Update(his[i],his[i-1],0,1000000000,a,i+n);
    Query(his[i-1],0,1000000000,l,r,i);
}
printf("%d\n",ans-Dinic());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
19
2016
0

[BZOJ1483] [HNOI2009]梦幻布丁

链表启发式合并

每次将元素少的并到多的上面

注意维护一下每个链表维护的真实颜色就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1500005;

int n,m,a[N],siz[N],f[N],ans;

struct Line{
int pos;
Line *next;
Line(){}
Line(int x,Line *y){pos=x;next=y;}
}*color[N];

void Add(int x,int pos){Line *tp=new Line(pos,color[x]);color[x]=tp;}

void Merge(int x,int y){
if(x==y)return;
if(siz[f[x]]>siz[f[y]])swap(f[x],f[y]);
x=f[x];y=f[y];
if(!color[x])return;
for(Line *i=color[x];i;i=i->next){if(a[i->pos-1]==y)ans--;if(a[i->pos+1]==y)ans--;}
for(Line *i=color[x];i;i=i->next)a[i->pos]=y;
Line *Tp;
for(Tp=color[x];Tp->next;Tp=Tp->next);
Tp->next=color[y];color[y]=color[x];color[x]=NULL;
siz[y]+=siz[x];siz[x]=0;
}

int main(){
freopen("1483.in","r",stdin);
freopen("1483.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[a[i]]=a[i];siz[a[i]]++;Add(a[i],i);if(a[i]!=a[i-1])ans++;}
for(int i=1;i<=m;i++){
	int opt,x,y;
	scanf("%d",&opt);
	if(opt==1){scanf("%d %d",&x,&y);Merge(x,y);}
	if(opt==2)printf("%d\n",ans);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
19
2016
0

[BZOJ1015] [JSOI2008]星球大战starwar

水并查集

时光倒流就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
 
int f[400005],n,m,k,del[400005],cnt,star[400005],ans[400005];
vector<int> V[400005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){f[x]=y;}
 
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){int x,y;scanf("%d %d",&x,&y);x++;y++;V[x].push_back(y);V[y].push_back(x);}
scanf("%d",&k);
cnt=n-k;
for(int i=1;i<=k;i++){
    scanf("%d",&star[i]);
    del[++star[i]]=1;
}
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=n;i++){
    if(del[i])continue;
    for(int j=0;j<V[i].size();j++){
        if(!del[V[i][j]] && Find(i)!=Find(V[i][j])){cnt--;Union(Find(i),Find(V[i][j]));}
    }
}
ans[k+1]=cnt;
for(int i=k;i;i--){
    cnt++;del[star[i]]=0;
    for(int j=0;j<V[star[i]].size();j++){if(!del[V[star[i]][j]] && Find(V[star[i]][j])!=Find(star[i]))cnt--,Union(Find(star[i]),Find(V[star[i]][j]));}
    ans[i]=cnt;
}
for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
18
2016
0

[BZOJ2154] Crash的数字表格

我做这题的经历告诉了我:不要乱取模

多取了一个mod 然后WA无数次

我这个方法并不是最优的

懒得写题解了

iwtwiioi大爷的题解

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const long long Mod=20101009ll;
int mu[10000005],pri[10000005],cnt,tab[10000005];
long long n,m,ans,s[10000005],Mn;

long long Sum(long long x,long long y){return ((x*(x+1)/2)%Mod)*((y*(y+1)/2)%Mod)%Mod;}

void Prepare(){
mu[1]=1;
Mn=min(n,m);
for(long long i=2;i<=Mn;i++){
	if(!tab[i]){pri[++cnt]=i;mu[i]=-1;}
	for(long long j=1;j<=cnt && i*pri[j]<=Mn;j++){
		tab[i*pri[j]]=1;
		if(i%pri[j]){mu[i*pri[j]]=-mu[i];}
		else {mu[i*pri[j]]=0;break;}
	}
}
for(long long i=1;i<=Mn;i++)s[i]=(s[i-1]+(i*i*mu[i])%Mod)%Mod;
}

long long F(long long x,long long y){
long long j,ans=0,Mn2=min(x,y);
for(long long i=1;i<=Mn2;i=j+1){
	j=min(x/(x/i),y/(y/i));
	ans=(ans+(s[j]-s[i-1])*Sum(x/i,y/i)%Mod)%Mod;
}
return ans;
}

int main(){
freopen("2154.in","r",stdin);
freopen("2154.out","w",stdout);
scanf("%lld %lld",&n,&m);
Prepare();
long long j;
for(long long i=1;i<=Mn;i=j+1){
	j=min(n/(n/i),m/(m/i));
	ans=(ans+(j+i)*(j-i+1)/2%Mod*F(n/i,m/i)%Mod)%Mod;
}
printf("%lld\n",(ans+Mod)%Mod);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
18
2016
0

[BZOJ3522] [Poi2014]Hotel

这题是树形DP

暴力枚举三个点的中点

因为每个点的深度在以这个点为根的子树中的深度都一样

所以我们开三个数组维护就可以了

时间复杂度$O(n^2)$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,en,h[5005],tx1[5005],tx2[5005],dep[5005],mx_dep;
long long ans=0;

struct Edge{
int b,next;
}e[10005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Dfs(int u,int fa,int deep){
mx_dep=max(mx_dep,deep);
dep[deep]++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa)Dfs(v,u,deep+1);
}
}

int main(){
freopen("3522.in","r",stdin);
freopen("3522.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
	int x,y;
	scanf("%d %d",&x,&y);
    AddEdge(x,y);AddEdge(y,x);
}
for(int i=1;i<=n;i++){
	memset(tx1,0,sizeof(tx1));
	memset(tx2,0,sizeof(tx2));
	for(int j=h[i];j;j=e[j].next){
		memset(dep,0,sizeof(dep));
		int v=e[j].b;
		Dfs(v,i,1);
		for(int k=1;k<=mx_dep;k++){
			ans+=tx2[k]*dep[k];
			tx2[k]+=dep[k]*tx1[k];
			tx1[k]+=dep[k];
		}
	}
}
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
17
2016
0

AHOI2016 滚粗记

至于AH队的名单还是不发为好。。毕竟总成绩没有确定

Day 0

到了合肥

下午试机写了一个网络流

晚上隔膜

Day 1

早上考试

三个数据结构

直接滚粗

10+0+30

下午隔膜+KFC

晚上看模版

Day 2

早上考试

两个数据结构一个计算几何

直接弃疗

40+10+30

总分120

lyz进队了

slx day2全省rank4

wyx好像没进队。。默哀

AHOI2017,刷题一年,明年再战!

Category: 随笔 | Tags: 随笔
4
15
2016
0

[BZOJ2105] 增强型LCP

因为修改的次数比较少,所以每次暴力重构hash就可以了

LCP可以用二分来做

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

const unsigned long long Mod1=131ll,Mod2=171ll;

int n,q;
string s;
char ch[1000005];
unsigned long long hash1[1000005],hash2[1000005],Pow1[1000005],Pow2[1000005];

void MakeHash(){
n=s.length();
hash1[n-1]=s[n-1];
hash2[n-1]=s[n-1];
for(int i=n-2;i>=0;i--){
    hash1[i]=hash1[i+1]*Mod1+s[i];
    hash2[i]=hash2[i+1]*Mod2+s[i];
}
}

void Prepare(){
Pow1[0]=1ll;
Pow2[0]=1ll;
for(int i=1;i<=1000000;i++){
    Pow1[i]=Pow1[i-1]*Mod1;
    Pow2[i]=Pow2[i-1]*Mod2;
}
}

pair<unsigned long long,unsigned long long> GetHash(int l,int len){
return make_pair(hash1[l]-hash1[l+len]*Pow1[len],hash2[l]-hash2[l+len]*Pow2[len]);
}

int LCP(int a,int b){
if(a>b)swap(a,b);
int l=0,r=n-b;
while(l<=r){
    int mid=l+r>>1;
    if(GetHash(a,mid)!=GetHash(b,mid))r=mid-1;
    else l=mid+1;
}
return r;
}

int main(){
freopen("2105.in","r",stdin);
freopen("2105.out","w",stdout);
scanf("%d %d",&n,&q);
scanf("%s",ch);s=ch;
Prepare();
MakeHash();
while(q--){
    char opt[10];
    scanf("%s",opt);
    if(opt[0]=='L'){
        int l,r;
        scanf("%d %d",&l,&r);
        l--;r--;
        printf("%d\n",LCP(l,r));
    }
    if(opt[0]=='A'){
        int x;
        scanf("%d %s",&x,ch);
        x--;
        s.insert(x,ch);
        MakeHash();
    }
    if(opt[0]=='C'){
        int x,y;
        scanf("%d %d %s",&x,&y,ch);
        x--;y--;
        for(int i=x;i<=y;i++)s[i]=ch[i-x];
        MakeHash();
    }
    if(opt[0]=='D'){
        int x,y;
        scanf("%d %d",&x,&y);
        x--;y--;
        s.erase(x,y-x+1);
        MakeHash();
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
14
2016
0

[BZOJ2427] [HAOI2010]软件安装

这题如果没有环的话就是一个依赖背包问题,可以树形DP

有环就用tarjan缩点就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int en,en2,h[105],h2[105],w[505],v[105],d[105],low[105],dfn[105],n,m,scc,dp[105][505],cnt,Q[105],Qcnt,inQ[105],belong[105],sv[105],sw[105],in[105];

struct Edge{
int b,next;
}e[10005],e2[10005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void AddEdge2(int sa,int sb){
in[sb]=1;
e2[++en2].b=sb;
e2[en2].next=h2[sa];
h2[sa]=en2;
}

void Tarjan(int u){
dfn[u]=low[u]=++cnt;
Q[++Qcnt]=u;inQ[u]=1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}
    else if(inQ[v]){low[u]=min(low[u],dfn[v]);}
}
if(dfn[u]==low[u]){
	scc++;
	int nw=0;
	while(nw!=u){
		nw=Q[Qcnt--];inQ[nw]=0;
		belong[nw]=scc;
		sv[scc]+=v[nw];
		sw[scc]+=w[nw];
	}
}
}

void Rebuild(){
for(int i=1;i<=n;i++){
	for(int j=h[i];j;j=e[j].next){
		int v=e[j].b;
		if(belong[i]!=belong[v]){
			AddEdge2(belong[i],belong[v]);
		}
	}
}
for(int i=1;i<=scc;i++){if(!in[i])AddEdge2(scc+1,i);}
}

void DP(int u){
for(int i=h2[u];i;i=e2[i].next){
	int v=e2[i].b;DP(v);
	for(int j=m-sw[u];j>=0;j--){
		for(int k=0;k<=j;k++){
			dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);
		}
	}
}
for(int j=m;j>=0;j--){
	if(j>=sw[u])dp[u][j]=dp[u][j-sw[u]]+sv[u];
	else dp[u][j]=0;
}
}

int main(){
freopen("2427.in","r",stdin);
freopen("2427.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=n;i++){
	scanf("%d",&d[i]);
	if(d[i])AddEdge(d[i],i);
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
Rebuild();
DP(scc+1);
printf("%d\n",dp[scc+1][m]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
14
2016
0

[BZOJ3555] [Ctsc2014]企鹅QQ

Hash水题,枚举每一位然后hash搞一搞

听说自然溢出很快就试了一下

然后就WAWA不休

最后还是回归正常的办法:模大数字(为什么不是质数呢?因为我的两个数字是随便敲的)

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

const long long Mod1=666666666666667ll,Mod2=233333333333333ll;

int n,len,x,ans=0;
long long Ha_F[30005][205],Ha_L[30005][205],tp[30005];
char s[30005][205];

void Get(int x){
for(int i=1;i<=len;i++)Ha_F[x][i]=(Ha_F[x][i-1]*233+s[x][i])%Mod1;
for(int i=len;i;i--)Ha_L[x][i]=(Ha_L[x][i+1]*137+s[x][i])%Mod2;
}

int main(){
freopen("3555.in","r",stdin);
freopen("3555.out","w",stdout);
scanf("%d %d %d",&n,&len,&x);
for(int i=1;i<=n;i++){
	scanf("%s",s[i]+1);
	Get(i);
}
for(int i=1;i<=len;i++){
	for(int j=1;j<=n;j++){
		tp[j]=(Ha_F[j][i-1]*Mod2+Ha_L[j][i+1]*Mod1)%(Mod2*Mod1);
	}
    sort(tp+1,tp+n+1);
    int cnt=1;
    for(int j=2;j<=n;j++){
		if(tp[j]==tp[j-1])ans+=cnt,cnt++;
		else cnt=1;
    }
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com