题目大意&链接：
http://codeforces.com/problemset/problem/718/E
给一个长为n（n<=100 000）的只包含‘a’~‘h’8个字符的字符串s。两个位置i,j(i!=j)存在一条边，当且仅当|i-j|==1或s[i]==s[j]。求这个无向图的直径，以及直径数量。
题解：
命题1：任意位置之间距离不会大于15。
证明：对于任意两个位置i，j之间，其所经过每种字符不会超过2个（因为相同字符会连边），所以i，j经过节点至多为16，也就意味着边数至多为15。
然后我们对于每个节点，需要计算出其与其他节点距离，当然为了不重复，只需考虑pos小于当前节点的位置。此时我们分为两种情况：
1.|i-j|<=15;
2.|i-j|>15。
对于第一种我们是取|i-j|与i先到达一种字母，j也到达这种字母距离和取较小值。所以我们设
$F[i][c]$表示i节点到达c这种字母的最小距离。即i到j的距离为：$min(|i-j|,F[i][c]+1+F[j][c])$。
命题2：i与j到达的同一种字母的位置如果相同，一定不是最优解。
证明：假设到达同一个位置，那么只可能是通过这个位置的左右两个节点。那么，对于到达左右这两个节点如果其路径之间不存在相同的字母，那么其距离和|i-j|相同，如果存在相同字母，则一定比当前方式短。综上所述，到达同一位置一定不是最短路。
对于第二种，我们由命题1可知，其距离不会大于15。我们再来看一个命题：
命题3：设$dis[c1][c2]$表示c1字母到达c2字母的最小距离，那么我们有，若$s[i]==c1$，则$dis[c1][c2]<=F[i][c2]<=dis[c1][c2]+1$。
证明：这个……显然吧？
我们此时考虑对于第二种情况下的j，|i-j|一定不是最短的，所以一定是从$F[i][c]+1+F[j][c]$中选取最小值，那么由命题3可知，我们并不需要其确切位置，仅需知道$F[i][c]$与$dis[ci][c]$之间的关系，然后我们可以用一个二进制数$mark[j]$来表示其与$dis[cj][c]$之间的关系，然后我们把关系相同（即mark[j]相同）的j统计其数量，然后再求一下此时i与某一种mark之间的最短路即可。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=;
int n,f[N][],dis[][];
char s[N];
int q[N],d[N];
int mark[N];
int c[N][<<];
inline void bfs(int c){
int l=,r=;
for(int i=;i<=n;i++)if(s[i]-'a'==c){
q[r++]=i,d[i]=;
}else d[i]=-;
bool vis[]={};
vis[c]=true;
while(l<r){
int now=q[l++];
if(!vis[s[now]-'a']){
vis[s[now]-'a']=true;
for(int i=;i<=n;i++)
if(s[i]==s[now]&&d[i]==-){
d[i]=d[now]+;
q[r++]=i;
}
}
if(now>&&d[now-]==-) q[r++]=now-,d[now-]=d[now]+;
if(now<n&&d[now+]==-) q[r++]=now+,d[now+]=d[now]+;
}
for(int i=;i<=n;i++)
if(d[i]!=-)f[i][c]=d[i];
}
int main(){
// freopen("1.out","w",stdout);
scanf("%d",&n);
scanf("%s",s+);
memset(f,0x3f,sizeof(f));
for(int i=;i<;i++)
bfs(i);
memset(dis,0x3f,sizeof(dis));
for(int i=;i<=n;i++)
for(int j=;j<;j++)
dis[s[i]-'a'][j]=min(dis[s[i]-'a'][j],f[i][j]);
for(int i=;i<=n;i++) for(int j=;j<;j++)
if(f[i][j]>dis[s[i]-'a'][j]) mark[i]|=<<j;
// for(int i=1;i<=n;i++)
// printf("mark[%d]=%d\n",i,mark[i]);
int ans=;
long long cnt=;
for(int i=;i<=n;i++){
for(int j=max(i-,);j<i;j++){
int now=i-j;
for(int k=;k<;k++)
now=min(now,f[j][k]++f[i][k]);
if(now==ans) cnt++;
if(now>ans) ans=now,cnt=;
}
int t=i-;
if(t>=) c[s[t]-'a'][mark[t]]++;
for(int j=;j<;j++) for(int k=;k<;k++)
if(c[j][k]){
int now=0x7fffffff;
for(int l=;l<;l++){
now=min(now,dis[j][l]++f[i][l]+((k&(<<l))>>l));
//printf("%d\n",(k&(1<<l))>>l);
}
if(now==ans) cnt+=c[j][k];
if(now>ans) ans=now,cnt=c[j][k];
}
}
printf("%d %lld\n",ans,cnt);
}