題目傳送門

博客傳送門

曾經某位大佬說過，計數類問題一般考慮排列組合或dp。它看起來不像是排列組合的題目，所以考慮dp。

0.消消樂序列

我們發現這個可消串類似一個括號匹配。于是類似地，我們定義消消樂序列如下：

1.空串是一個合法的消消樂序列。

2.對于任意消消樂序列 A，SAS 是一個合法的消消樂序列，其中 S 為任意一個小寫字符。

3.對于任意消消樂序列 A,B，AB是一個合法的消消樂序列。

4.任意一個消消樂序列均可以通過以上方式構造出來。

原問題等價于求原串有多少非空連續子串是消消樂序列。

1.dp轉移方程式

設 \(dp_i\) 表示以 \(i\) 結尾的消消樂序列的個數，再設 \(lst_i\) 表示最大的使得 \([lst_i,i]\) 為消消樂序列的數。

根據性質 3，所有以 \(lst_i-1\) 為結尾的消消樂序列都可以拼接上這個消消樂序列，變成以 \(i\) 為結尾的消消樂序列。而這個序列本身也是個消消樂序列。所以狀態轉移方程為 \(dp_i=dp_{lst_i-1}+1\)。

為什么我們要求 \(lst_i\) 最大呢？

考慮如圖所示的情況。此時 \([j,i]\)，\([lst_i,i]\) 均為消消樂序列。

然后我們就發現，如果按照剛才的遞推式是忽略了 \([lst_i,i]\) 這個序列的。如果改用其他轉移方程，也不好寫轉移方程式或者時間復雜度不優。

2.暴力跳

那如何求 \(lst_i\) 呢？或者說，如果我們求完了 \(i\) 的各種信息，怎么求 \(lst_{i+1}\) 呢？

第一種情況類似于 abcddcba，\(s_{i+1}=s_{lst_i-1}\)，也就是 \(s_{lst_i-1}\) 和 \(s_{i+1}\) 可以把 \([lst_i,i]\) 這個序列包起來，形成一個新的合法序列。那我們直接跳到 \(lst_i-1\)，并令 \(lst_{i+1}=lst_i-1\) 就好了。

第二種情況類似于 dabbaceffecd，當前 \(i+1\) 在第二個 \(d\) 處。那我們跳了一段合法序列 \([lst_i,i]\) 后，發現 \(s_{lst_i-1}\) 和 \(s_{i+1}\) 并不能把該序列包起來。

這說明什么，說明 \(i+1\) 與 \(lst_{i+1}\) 之間隔了很多個消消樂序列，那我們就接著暴力往后跳，跳過 \([lst_{lst_i},lst_i]\) 再次檢查，再不行就跳過 \([lst_{lst_{lst_i}},lst_{lst_i}]\)……

總之，我們一個消消樂序列一個消消樂序列地往后跳，直到找到一個位置可以和它包住前面的消消樂序列。或者跳到序列以外，說明并沒有以 \(i+1\) 結尾的消消樂序列。

3.時間復雜度

本題題解區還是有很多大佬證明過這個東西的，本蒟蒻也淺淺證明一下這個東西是 \(O(n|S|)\) 的叭。

我們的核心思路就是證明，對于點 \(i\) 和某種字符 \(S\)，只會有 1 個點 \(j\) 跳到點 \(i\)。

反證法，假設 \(k\) 和 \(j\) 兩個位置都能跳到 \(i\)，并且 \(s_j=s_k,k>j\)。這說明 \([i+1,j-1]\) 和 \([i+1,k-1]\) 都是消消樂序列。那根據性質 3 的變形，他們相減后的區間 \([j,k-1]\) 也是消消樂序列。

這樣的話肯定會存在一個最小的 \(t \in (j,k-1]\)，\([j,t]\) 是消消樂序列（最起碼 \(t=k-1\) 滿足條件）。如果 \(t=k-1\)，那 \(k\) 第一次跳的時候就直接滿足條件退出了。

否則的話 \([t+1,k-1]\) 是個消消樂序列，\(i < j < t \le lst_k\)（當 \([t+1,k-1]\) 是極短消消樂序列時取等），\(k\) 也不可能跳到 \(i\)。

綜上，原結論成立。所以每個位置最多被跳 26 次，時間復雜度 \(O(n|S|)\)。

代碼極其簡短，如下所示：

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<48){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

const int N=2e6+6;
int n,dp[N],lst[N];
char s[N];

signed main(){
	n=read();
	scanf("%s",s+1);
	int ans=0;
	for(int i=2;i<=n;i++){
		for(int j=i-1;j>0;j=lst[j]-1){//暴力跳一個消消樂序列 
			if(s[j]==s[i]){
				lst[i]=j;
				break;
			}
		}
		if(lst[i]){//存在以 i 為結尾的消消樂序列 
			dp[i]=dp[lst[i]-1]+1;
			ans+=dp[i];
		}
	}
	printf("%lld",ans);
	return 0;
}

參考資料：

1.洛谷題解1

2.洛谷題解2