[ARC180A] ABA and BAB 题解
思路
容易发现，如果我们能把原串分解成互不干扰的部分，那么，我们就可以用乘法原理求解。
什么部分是干扰的？什么部分是不干扰的？
如 ABA 与 BAB 就是互相干扰的部分 ，因为拼接后的 ABABAB 的方案数比分别计算 ABA 和 BAB 的方案数再相乘不同，可以自己手动尝试一下。
容易发现，我们可以将连续的 AB 串分为一个部分，证明如下（并不严谨）：
如果我们不能将连续的 AB 串分为一个部分，那么有两种可能：
- 这个串的其中一个子串会被两个部分分解。
- 这个串和与它相邻的串是互相干扰的。
第一种可能
上面提到，这样的两个部分互相干扰（比如
ABA与BAB，将ABA替换成A，或者是将BAB替换成B，对于原串来讲，只有一种方案数），所以我们不能将这样的一个字串分成两部分。
如果把这个子串变成是单独的一部分，会有如下情况（这里的原串指上面的连续 AB 串）：
- 这个子串就是原串：没有任何事。
- 这个子串不是原串：那么必将还有其他子串，相邻的两个子串又是更大的子串的分解，根据上面的说法，是不行的。所以，这两个子串又需要并成一个串。
通过最终的不断合并，终究会合并成原串。
所以，这个串的其中一个子串不会被两个部分分解。
第二种可能
我们刚才一直在说 干扰 ，意思似乎手造一造就懂了，但是在这里不行，我们需要 更严谨 的定义。
什么串是互相干扰的？通过刚才讲解的第一种可能，我们发现，互相干扰的串满足一种性质：
- 虽然两个串好像可以互相单独计算，但是一些方案对于原串来讲，就只有一种方案数。
我们发现，如果这两个串拼接后，是一个连续的 AB 串，那么，你不管是对左边还是对右边做操作，都一样。
为什么哪？
观察替换：
ABA\rightarrow A。BAB\rightarrow B。
这不就是删除一个 AB 串吗？
那么，一个连续的 AB 串对左边或对右边做操作，就都等价于删掉一个 AB 串。
由于连续 AB 串是由若干个 AB 串加某些字符组成，做出以下分类讨论：
- 没有加任何字符。删除任意地方的一个
AB串还是由若干AB串组成，并没有改变顺序。 - 有时开头多一个
B，或结尾多一个A，或两个都有。但我们也只是删除中间的字符（够不到），所以依旧是若干个AB串加这些字符组成，并没有改变它们的顺序。
这里的顺序仅仅是指 AB 串与多余字符之间的位置关系。
刚刚我们说了，如果这两个串拼接后，是一个连续的 AB 串，那么，你不管是对左边还是对右边做操作，都一样。
所以，如果这两个串拼接后是一个连续的 AB 串，它们互相干扰，反之不干扰（这里我就不证明了，可以按照我的方法试着证明）。
如果这两个串拼接后是一个连续的 AB 串，那么，我们找的连续 AB 串不应该是这个，这是不可能的。
所以，这个串和与它相邻的串是不互相干扰的。
综上所述，我们可以将连续的 AB 串分为一个部分。
那么，剩下的就是一个问题了：
- 连续 AB 串的方案数是多少？
容易发现，每次操作都是删除一个 AB 串，好像是
但是
怎么办？
很简单，变成
为了编码简便，可以变成
代码
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n;
string s;
string t;
int ans=1;
int cal(string t){
//cal蕴含着我们的人类智慧（cal的可行性，什么条件下使用cal，cal的计算过程）
return (t.size()+1)/2;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
cin>>s;
for(int i=0;i<n;i++){
if(t!=""&&t[t.size()-1]==s[i]){//不是连续AB串了
ans=(ans*cal(t))%mod;//乘法原理
t="";
}
t+=s[i];
}
ans=(ans*cal(t))%mod;//最后可能还有剩余
cout<<ans;
return 0;
}