对于一种排列方案，答案显然等于相邻字符在环上对应的劣弧长度之和。
然后其实你可能会想到很多状压 / 折半搜索方法，包括但不限于枚举一半的信息然后折半搜后一半，但稍加思考会发现这些方案都避不开记录元素之间的相对顺序，而但凡涉及到这一点，复杂度都是阶乘起步。因此我们只能另辟蹊径。
考虑 \(k\) 是偶数的情况。对于 \(i\) 与 \(i\bmod k\) 位置之间的弧，考虑与其距离 \(\dfrac{k}{2}\) 的那段弧，有一个非常重要的性质是，考察这两段弧将圆周分成的两部分，假设两部分中的字母集合分别是 \(S,T\)，那么这两个弧被经过的次数之和等于 \(\sum\limits_{x\in S}\sum\limits_{y\in T}c_{x,y}+c_{y,x}\)，其中 \(c_{x,y}=\sum\limits_{i=2}^n[s_{i-1}=x][s_i=y]\)。这样我们考虑枚举 \(1\) 和 \(\dfrac{k}{2}+1\) 将圆周分成的两部分对应的字符集合 \(S,T\)，然后顺着环一遍 DP 即可。转移的时候比较 naive 的方法是枚举一个属于 \(S\) 但不在当前状态中的点 \(x\)，和一个属于 \(T\) 且在当前状态中的点 \(y\)，删除 \(x\) 并加入 \(y\)，但这样是 \(k^2\) 的，被卡掉了。优化方法是类似于设计辅助数组 \(g\)，先删除 \(S\) 元素时执行转移 \(f\to g\)，加入 \(T\) 元素时执行转移 \(g\to f\)，这样转移可以降到 \(O(k)\)。这样总复杂度是 \(\dbinom{k}{k/2}^2·k\)，好像刚好可以卡过去。
对于 \(k\) 是奇数的情况也是类似的，只不过要对所有 \(i\in[1,k]\) 都算一遍贡献然后除以 \(2\)。
实际实现并不用记两个辅助数组，可以直接通过 __builtin_parity 判断是 \(f\) 还是 \(g\)，具体细节见代码。
const int MAXN=16;
const int MAXL=1e5;
const int MAXP=65536;
const int INF=0x3f3f3f3f;
int n,len,c[MAXN+3][MAXN+3],coef[MAXP+5];char s[MAXL+5];
struct dat{
int mn;ll num;
dat(){mn=num=0;}
dat(int _mn,ll _num){mn=_mn;num=_num;}
}dp[MAXP+5],ans;
dat operator +(dat a,dat b){
if(a.mn!=b.mn)return (a.mn<b.mn)?a:b;
else return dat(a.mn,a.num+b.num);
}
dat inc(dat a,int v){return dat(a.mn+v,a.num);}
int main(){
scanf("%d%d%s",&n,&len,s+1);
for(int i=2;i<=len;i++)if(s[i]!=s[i-1])c[s[i-1]-'a'][s[i]-'a']++;
for(int i=1;i<(1<<n);i++)for(int j=0;j<n;j++)if(i>>j&1)
for(int k=0;k<n;k++)if(~i>>k&1)coef[i]+=c[j][k]+c[k][j];
ans=dat(INF,0);
for(int s=1;s<(1<<n);s+=2)if(__builtin_popcount(s)==(n+1)/2){
for(int i=0;i<(1<<n);i++)dp[i]=(i==1)?dat(coef[s],1):dat(INF,0);
for(int t=1;t<(1<<n);t++)if(dp[t].num){
if(__builtin_parity(t)){
for(int i=0;i<n;i++){
if((s>>i&1)==0&&(t>>i&1)==0){
int nxt=t^(1<<i);
if(n&1)dp[nxt]=dp[nxt]+inc(dp[t],coef[s^t]);
else dp[nxt]=dp[nxt]+dp[t];
}
}
}else{
for(int i=0;i<n;i++){
if((s>>i&1)==1&&(t>>i&1)==0){
int nxt=t^(1<<i);
dp[nxt]=dp[nxt]+inc(dp[t],coef[s^t]);
}
}
}
}ans=ans+dp[(1<<n)-1];
}printf("%d\n%lld\n",ans.mn/(1+n%2)+len,ans.num);
return 0;
}