CF578D LCS Again

一道胡搞题。
考虑枚举串$S,T$的最长公共前缀（LCP）和最长公共后缀(LCS)。

差代表比对出来的不一样的位置。两个红色的矩形代表的字符串是一样的。两个叉一定是紧贴着LCS或者LCP的（如果不是的话LCP和LCS还能接着移动，就不是枚举到的LCP/LCS了）。

还有另外一种情况就是上面的叉在后面，下面的叉在前面，和上面那幅图正好相反。

因为上面那个字符串$S$是固定的，而且矩形和LCP/LCS部分的字符也是固定的，唯一不固定的就只有下面的叉了。有因为下面的叉不能等于上面的字符，所以这个不固定的叉一共有$m-1$种方案来放置字符。

所以每个可行的LCP,LCS的组合对方案数都有$m-1$的贡献。“可行的LCP，LCS”是指，的确存在这种状态。因为字符串$S$中的叉是什么字符是固定的。而它下面对应的字符，也是固定的，而且一定为它后面的字符（因为两个矩形代表的串是相等的）。所以一个$LCP,LCS$组合成立的充要条件是：“上面那个叉和他后面的字符相同”。上面的叉在后面，下面的叉在前面的情况类似，充要条件变成了“上面那个叉和他前面的字符相同”

这个东西显然是能$O(n)$扫一遍搞完的。但是我们发现对于有些LCP，LCS的组合，它对两幅图的情况都成立，他就会被计算两次。所以我们需要求这种情况的出现次数然后容斥掉。我们发现对于这种情况，中间的那部分字符串一定是形如$abababa$这样的。因为对于上面的每个字符，都要等于他左下和右下的字符。

我们可以先$O(n)$扫出所有的极长的两个字符的串，然后用等差数列求和算出每个极长的串有多少个子串即可。具体可以看代码。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#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;
}