一道胡搞题。
考虑枚举串的最长公共前缀(LCP)和最长公共后缀(LCS)。
差代表比对出来的不一样的位置。两个红色的矩形代表的字符串是一样的。两个叉一定是紧贴着LCS或者LCP的(如果不是的话LCP和LCS还能接着移动,就不是枚举到的LCP/LCS了)。
还有另外一种情况就是上面的叉在后面,下面的叉在前面,和上面那幅图正好相反。
因为上面那个字符串是固定的,而且矩形和LCP/LCS部分的字符也是固定的,唯一不固定的就只有下面的叉了。有因为下面的叉不能等于上面的字符,所以这个不固定的叉一共有种方案来放置字符。
所以每个可行的LCP,LCS的组合对方案数都有的贡献。“可行的LCP,LCS”是指,的确存在这种状态。因为字符串中的叉是什么字符是固定的。而它下面对应的字符,也是固定的,而且一定为它后面的字符(因为两个矩形代表的串是相等的)。所以一个组合成立的充要条件是:“上面那个叉和他后面的字符相同”。上面的叉在后面,下面的叉在前面的情况类似,充要条件变成了“上面那个叉和他前面的字符相同”
这个东西显然是能扫一遍搞完的。但是我们发现对于有些LCP,LCS的组合,它对两幅图的情况都成立,他就会被计算两次。所以我们需要求这种情况的出现次数然后容斥掉。我们发现对于这种情况,中间的那部分字符串一定是形如这样的。因为对于上面的每个字符,都要等于他左下和右下的字符。
我们可以先扫出所有的极长的两个字符的串,然后用等差数列求和算出每个极长的串有多少个子串即可。具体可以看代码。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=100200;
char s[maxn];
int n,m;
ll ans;
ll calc(int len){
return 1ll*(1+len-1)*(len-1)/2;
}
int main(){
scanf("%d%d%s",&n,&m,s+1);
rep(i,1,n-1){
if(s[i]!=s[i+1]){
ans+=n-i;
}
}
rep(i,2,n){
if(s[i]!=s[i-1]){
ans+=i-1;
}
}
ans+=n;
ans*=m-1;
rep(i,1,n-1){
char bk[2];bk[1]=s[i],bk[0]=s[i+1];
if(bk[1]==bk[0])continue;
int cnt=1,now=i;
while(now<n&&bk[((cnt%2)^1)]==s[now+1]){
now++;cnt++;
}
i=now-1;
ans-=calc(cnt);
}
cout<<ans;
return 0;
}