题解：AT_arc180_a [ARC180A] ABA and BAB

· · 题解

题目传送门

题目分析

arc 经典人类智慧题。

前置知识：乘法原理。

简单介绍一下，就是如果两个事件之间互不干扰，则它们的方案数总和就是它们各自的方案数的乘积。

为了方便，我们将 ABABA 这样的串叫做模板串。

先思考一个简单情况：一段极长的连续的 ABABA 或 BABAB 的方案数。

我的思考过程：

ABA，ABAB 有两种方案；ABABA，ABABAB 有三种方案；ABABABA，ABABABAB 有四种方案。

找到规律了么？设该模板串的长度为 n，那么它的方案数为 \lceil {n \over 2} \rceil。

简单证明一下，如果有 k 个 ABA 这样的串，那么它就有 k+1 种方案，并且在结尾添加一个 B 不会影响方案数，因为我们是计算有多少个 ABA 转换了，而长度为 n 的模板串有 \lceil {n \over 2 } \rceil -1 个 ABA ，所以就有 \lceil {n \over 2} \rceil 个方案。

接下来，思考更一般的形式，我们会发现，两个模板串之间互不干扰，所以应使用乘法原理。

接下来是代码时间！

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long//不开long long见祖宗
const int mod=1e9+7;
int n,ans=1;
char c[250005];
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    int sze=0;
    for(int i=1; i<=n; i++)
    {
        cin>>c[i];
        if(c[i]!=c[i-1]) sze++;//计算该模板串的长度
        else ans=(((sze/2)%mod+sze&1)%mod*ans)%mod,sze=1;//计算贡献
    }
    ans=(((sze/2)+sze&1)%mod*ans)%mod;//别忘了最后一个模板串的贡献
    cout<<ans;
    return 0;
}