题解 [AGC033E] Go around a Circle

· · 题解

设给定字符串为 S，构造串为 T。

不妨设 S_1=R，若为 B，则取反整个 S，两串等价。

此时 T 中显然不能存在相邻的 B，否则只需要在开始时将棋子放在 B 之间即可使得 S_1 无法取得。由此可知 T 一定是由若干个「连续 R 加单独 B」 组成的。

考虑策略会是怎样的，设初始放棋子的位置左侧有 x 个 R，右侧有 y 个 R，则如果当前 S 开头一段 R 长度为奇数 k，我们会挑 x,y 中为奇数且不大于 k 的一个作为方向前进，因为我们需要保证在走完这段 S 中的 R 之前走到棋子所在 R 段的边界，且在走完时刚好在边界，这意味着我们要做出两个限制：

除此之外，发现我们每次走完 S 中的一段 B 后走到一段新的 R 时，若该 R 段为偶数，则显然棋子可以左右横跳，对其没有任何限制；若为奇数 k，则还需满足 T 中所有 R 段长度都不大于 k。

注意此时我们有一点需要特殊判断，即当 S 中全为 R 时，由于无需走到 R 段边界，故没有任何限制，单独做 dp 计数有多少环由若干无限制 R 段和单独 B 组成即可。

而对于非全 R 的情况，我们先综上所述找到 R 段长度的上界，然后设 dp_i 表示状态，枚举最后一段段长转移即可，注意由于两种方案旋转后相同不算一种方案，所以我们还需要将每一种方案乘上开头段的长度。

本题再次启发我们在无从下手时，要仔细分析题目性质，通过增加限制减少决策的方式，解决转化后的问题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
int n,m;
char s[N];
ll dp[N],sum[N],f[N][2];
bool flag1,flag2;
int read(){
    int w=0,fh=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') fh=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*fh;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    n=read(),m=read();
    scanf("%s",s+1);
    if (s[1]=='B'){
        for (int i=1;i<=m;i++)
            s[i]=(s[i]=='B')?'R':'B';
    }
    int minn=1e9;
    for (int i=1,len=0,hav=1;i<=m;i++){
        if (s[i]=='B'){
            if (len&1||hav) minn=min(minn,len);
            len=0,hav=0;
        }else ++len;
        if (s[i]=='B') flag1=1;
        else if (s[i]=='R') flag2=1;
    }
    if (!flag1||!flag2){
        ll ans=0;
        f[1][0]=1;
        for (int i=2;i<=n;i++)
            f[i][0]=(f[i-1][0]+f[i-1][1])%mod,f[i][1]=f[i-1][0];
        ans=(f[n][0]+f[n][1])%mod;
        f[1][0]=0,f[1][1]=1;
        for (int i=2;i<=n;i++)
            f[i][0]=(f[i-1][0]+f[i-1][1])%mod,f[i][1]=f[i-1][0];
        ans=(ans+f[n][0])%mod;
        cout<<ans<<"\n";
        return 0;
    }
    if (n&1){
        puts("0");
        return 0;
    }
    n/=2,minn=minn/2+1;
    for (int i=1;i<=minn;i++) dp[i]=2*i;
    for (int i=1;i<=n;i++){
        dp[i]=(dp[i]+sum[i-1])%mod;
        if (i-minn-1>=0) dp[i]=(dp[i]-sum[i-minn-1]+mod)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
        // cout<<dp[i]<<"\n";
    }
    cout<<dp[n]<<"\n";
    return 0;
}