Description
现在有一个长度为n的串S，其中每一个字母都是前m个小写字母
计算有多少个不同的长度为n的T（其中T也是由前m个小写字母组成），并且S与T的LCS为n-1
LCS就是同时存在于S和T的最长子序列
Input
第一行包含两个整数n和m表示S的长度和前m个小写字母
第二行是串S
Output
只要输出存在的T的数量
Sample Input
输入1：
3 3
aaa
输入2：
3 3
aab
输入3：
1 2
a
输入4：
10 9
abacadefgh
Sample Output
输出1：
6
输出2：
11
输出3：
1
输出3：
789
样例解释
第一个样例有6个可能的串T:aab,aac,aba,aca,baa,caa
第二个样例有11个可能的串T
Aaa,aac,aba,abb,abc,aca,acb,baa,bab,caa,cab
第三个样例只有b
Data Constraint
对于20%，n<=100
对于30%，n<=1000
对于40%，n<=10000
对于100%，n<=100000
题解
这题之前偷懒，不想打dp（不会），于是用了一个全新的方法（很简单）来做。
结果理解上一直出锅。
题解也写得有很多漏洞，于是在众大佬的帮助下成功找到一种理解方法：
第一步
我们要使新的串的lcs与原串相差1
那么我们考虑在原串中动手脚。
举个例子：
aaabacc
我们考虑把其中一个取出，再插入原串任意位置，然后改变字母，这样就可能得到一个合法的新串。
但是我们发现，取出第一个a与第二个a再放回是完全一样的。
那么意味着我们对于一段连续的字母，只能取出一个字母再放回。
那么就可以分分块：
|aaa|b|a|cc|
一共有4块。
考虑把第一块中取出一个a插入任意位置，并且更替位置：
假设放在b右边
变成aab"a"acc
然后把a变成不同的：aab"a"acc\aab"b"acc\aab"c"acc
显然有m种。
但是会有重复！
我们把a放在b的左边：aa"a"bcc\aa"b"bcc\aa"c"bcc
我们惊奇地发现，其中是有重复的情况的！
多画画就可以找到情况——对于每次插入，改变字母不能和左边的相同。
那么就可以有m-1种方案。
然而放在最开头时，可以放m种。
怎么办？但是我们发现，如果放在原来的块的最左边，（比如："a"aabacc、aaaba"c"c）这样虽然与左边的不同，但是也是不符合的。
所以加起来只有m-1种
总方案为：
第二步
我们考虑一个字符串——
n=8,m=3
aababacc
这个字符串我们可以求得方案为——
我们发现，原来的字符串变化可以取出第一块的一个a，放在第一个b后面——
ab"a"abacc
但是，把第一个b取出来放在第二个a左边，是一样的a"b"aabacc
然而这个在之前的情况是无法判断的。
具体怎么做？
对于ab这个字符串，会重复一次（把b放在a左边和a放在b右边一样）
对于ab"a"这个字符串，会重复三次（之前的一次，加上"a"放在b左边与b放在a右边，“a"放在a左边和b放在"a"左边）
对于ab"a”"b"这个字符串，会重复六次（之前三次，加上"b"放在"a"左边，"b"放在b左边，"b"放在a左边）
对于ababab……的情况，很好找规律吧？
所以，我们设一个P表示当前第i个位置，从当前位置往前的最长"abab……"的串长度为P。注意，这个字符串表示奇数位的字母相同，偶数位字母相同。
那么每次ans-P+1即可。
至于怎么证明这样就可以，感性理解理解。
如果你懂了怎么做，那么这个就是显然的。
var
i,j,k,l,n,m:longint;
ans:int64;
s:ansistring;
c1,c2:char;
begin
//assign(input,'lcs.in');reset(input);
//assign(output,'lcs.out');rewrite(output);
readln(n,m);
if n=1 then
begin
writeln(m-1);
halt;
end;
readln(s);
for i:=2 to n do
begin
if s[i-1]<>s[i] then
begin
ans:=ans+n*(m-1);
end;
end;
ans:=ans+n*(m-1);
j:=1;
for i:=2 to n do
begin
if j=1 then
begin
if s[i]<>s[i-1] then
begin
inc(j);
end;
end
else
begin
if (s[i]=s[i-2]) and (s[i]<>s[i-1]) then
begin
inc(j);
end
else
if (s[i]<>s[i-2]) and (s[i]<>s[i-1]) then
begin
j:=2;
end
else
if (s[i]=s[i-1]) then
begin
j:=1;
end;
end;
ans:=ans-j+1;
end;
writeln(ans);
end.