2019.3.23 提高A组 T3 JZOJ 4673 LCS Again

$Description$Description

现在有一个长度为$n$n的串$S$S，其中每一个字母都是前m个小写字母
计算有多少个不同的长度为$n$n的$T$T（其中$T$T也是由前$m$m个小写字母组成），并且S与T的LCS为$n-1$n−1
LCS就是同时存在于$S4和$S4和T$的最长子序列

$n\leq 100000$n≤100000

---

$Solution$Solution

荣斥瞎搞

---

$Code$Code

#include<cstdio>
#include<cstring>
using namespace std;int n,m,k;
char s[100001];
long long ans;
signed main()
{
	scanf("%d%d\n",&n,&m);
	scanf("%s",s+1);
	ans=n*(m-1);
	for(register int i=2;i<=n;i++) if(s[i]!=s[i-1]) ans+=n*(m-1);
	k=1;
	for(register int i=2;i<=n;i++)
	{
		if(k==1) {if(s[i]!=s[i-1]) k++;else continue;}
		else
		{
			if(s[i]==s[i-2]) k++;
			else
			{
				ans-=k*(k-1)/2;k=1;
				if(s[i]!=s[i-1]) k++;
			}
		}
	}
	ans-=k*(k-1)/2;
	printf("%I64d",ans);
}