AT_agc033_e [AGC033E] Go around a Circle 题解

Moya_Rao · 2026-06-19 20:20:13 · 题解

前言

感觉题解区都讲得怪深奥的喵，我这种小菜鸡当然是完全看不懂啦。于是在使用 AI 辅助后大战了一个下午总算搞懂了，写篇题解造福一下大家喵。

本篇题解比较长，讲解比较详细，希望你能耐心看完喵。如果某些部分你已经懂了可以选择跳过以节省时间喵。

题面分析

我绝不会告诉你我开这一栏的原因是因为我最开始压根就没看懂题。

题目说，给了一个有 n 条边、n 个点的圆，每条边的颜色只能为 \text{R} 或 \text{B}。给定了一个长度为 m 的字符串 S，要求我们计算有多少种边的颜色的分配方案，使得从圆上任意一个点出发，都能构造一条长度为 m 的路径（每步路可以沿着边往左或右走一步），且该路径上经过的边的颜色依次连起来与 S 相同。

两个很重要的点，第一点是从任何一个点出发都满足条件，第二点是要求构造一条完整路径（我最开始理解成了不同 S_i 可以选择不同的 i 步）。

核心思路

首先我们可以令 S_1 = \text{R}。看起来这样干是毫无道理的，但是并非，因为 \text{R} 和 \text{B} 颠倒是完全不会影响答案的。注意这里不是只把 S_1 改为 \text{R}，只是把 S_1 看做 \text{R}，那任何 S_i = S_1 的 S_i 也都是 \text{R}，而 S_i \not= S_1 的 S_i 则是 \text{B}。

原题目太复杂了！我们可以从简单的情况开始考虑。

特殊情况：S 全为 \text{R}

也就是纯色的情况！这意味着棋子任何时候都不能走到 \text{B} 的弧。

我会我会，这个是不是全部赋 \text{R} 就是对的，那么方案数就是 1！当然不对，只是棋子不能走 \text{B} 弧，没说不能有 \text{B} 的弧对不对呀。

事实上，只需保证不存在连续的大于等于 2 个 \text{B}，就一定是满足条件的。
为什么呢？首先考虑存在连续两个 \text{B} 的情况，这两条边之间一定夹了一个点 x。那只要让起点为 x 就会导致走不出去，而题目要求从任何点出发都能走出 S 路径，就被否了；接着考虑不存在连续两个 \text{B} 的情况，那么从任何点出发都一定有一个方向是 \text{R}，之后不需要再往外走了，直接在这条边上往返跑，反正最后得到的答案是一串 \text{R}。

一般情况：S 中存在 \text{B}

当 S 中包含 \text{B} 时，圆上的边的颜色设置就受到了不少限制，我们逐条来看看。

1. 圆上绝对不能出现长度为非 0 偶数长度的 \text{R} 连续段！

   • 看起来是一个非常奇怪的性质，简单证明一下。
   • 首先规定一个定义，从圆上某个顶点出发，为每个顶点分配奇偶性。这意味着有一个性质，当走奇数步后，一定抵达一个与起点奇偶性不同的点，反之走偶数步后，一定抵达一个与起点奇偶性相同的点。
   • 由于 \text{R} 数量是偶数，所以这段区间的左右两个端点节点的奇偶性一定相同。
   • 更形象地说，如果说左右端点都是奇数点，当 \text{B} 步数为偶数时，将最初的起点放置在偶数点上，那么偶数点走偶数步一定去到的还是偶数点，但想去到 \text{B} 得走到左右端点，左右端点都是奇数点！所以就被干掉了。
   • 反过来为什么长度是奇数就行呢，因为此时左右端点的奇偶性不同，这样就可以根据步数设置选择对应奇偶性的方向，就能完美完成每次要求啦。

2. 圆上还是不能出现连续的大于等于两个 \text{B}！

   • 吓哭了，这个不是特殊情况的限制吗，怎么到了一般情况还是适用啊！？
   • 首先如果存在两个连续的 \text{B} 且最开始的要求是 \text{R} 时就直接寄掉了，存在连续 \text{R} 且最开始要求 \text{B} 也会寄掉，这都是非常简单的，可以自己证一下。
   • 那我就故意卡你！两个 \text{B} 和一个 \text{R} 交替出现，并且最开始要求 \text{B} 呗，为什么也不行？因为你总会在某个时刻（题目要求 \text{B} 的时候）走到了两个 \text{B} 的中间，而 S 下一步又要求 \text{R}，你就走不出去了，那也寄掉了。
   • 那为什么单个就万无一失呢？前面保证过 \text{R} 不会被困住取不到 \text{B}，而只存在单个 \text{B}，所以不可能在某个位置发生“想要 \text{R} 但去不到”的情况啦。
3. - 事情越来越诡异了，奇数怎么你了，为什么奇数不行啊？ - 当然不行啦，因为我们要求的是奇数个 $\text{R}$ 和单个 $\text{B}$，因为是在圆上，两两可以匹配，其和都是偶数。若干个偶数的和肯定也是偶数啦！那 $n$ 也就必须是偶数啦。 - 因此此时如果 $n$ 是奇数就可以直接输出 $0$ 了，因为没有满足条件的构造。

4. 连续的一段 \text{R} 存在一个上限 L！

   • 当然了，如果不存在上限，意味着你可以弄无穷多个 \text{R}？当然不行啊！肯定是存在一个上限的啦，上限是多少呢？
   • 很简单啦！我们只需要找到 S 中限制最苛刻（长度最短，因此更新时是求 \min）的那一段区间，求出其长度，就是上限 L 啦。

实现方式

注意到前面只是列了一大坨性质，没有任何和实现方式挂钩的东西！这都无法写代码，所以接下来再说一下具体怎么实现，并附上每个片段的代码。

预处理：维护 L 值及相关信息

考虑遍历整个字符串 S 并开一个新的字符串，比如 s。这个 s 中，所有连续的 \text{B} 压缩为一个字符，而 \text{R} 会被逐个放出，目的是为了更好统计连续段 \text{R} 的数量来维护 L 值。

更舒服的做法是让 lst 维护当前 \text{R} 区间的左端点，这样实现时求区间长度会更加方便。

::::success[这部分的代码]

n=read(),m2=read();
cin>>str;str=" "+str;
L=n;//先赋值一个足够大的
s.resize(m2+1);
for(int i=1;i<=m2;i++){
    if(str[i]==str[1])//与开头字符相同
        s[++m]='R';//默认为 R
    else{//与开头字符不相同
        if(!m||s[m]!='B')s[++m]='B';//新开 B 段
        is_only=0;//肯定不止一种颜色了
    }
    if(m)lst[m]=(s[m]==s[m-1]?lst[m-1]:m);
    else lst[m]=1;
    //求出当前区间的左端点（起点）
    if(m>1&&s[m]=='B'&&s[m-1]=='R'&&((m-lst[m-1])&1))
        L=min(L,m-lst[m-1]);//如果该区间合法，则更新 L 值下界
}
for(int i=1;i<=m;i++)if(s[i]=='B'){
    //找到第一个 B 求前半段
    L=min(L,i-1ll+(i%2));//用前半段长度更新 L 值下界
    break;//只需要第一个 B，因此找到了就 break
}

::::

特殊情况：S 为纯色

纯色的情况下，就是要分配一些 \text{B} 使不存在相邻的 \text{B}，其他 \text{R} 可以随意分配（也不受前面 L 的限制，L 打的限制仅适用于一般情况）。

发现就是形如 Fibonacci 数列的信息，因为你需要考虑前面是填 \text{R} 还是 \text{B}，这就和 Fibonacci 爬楼梯的思想是类似的。把这个序列往前挪一格，令 dp_0 = 1 且 dp_1 = 1，后续 i \ge 2 则 dp_i = dp_{i-1} + dp_{i-2}，最终答案是 dp_n……

显然不对啊！因为我们现在是把圆环看做序列来做的，没有考虑首尾的情况，实际上答案是 dp_n + dp_{n-1} - dp_{n-3}。好奇怪的式子，为什么呢？

考虑它们的含义，dp_n 可以理解为以 \text{R} 开头的情况数（此时不存在首尾矛盾情况），dp_{n-1} 则是开头为 \text{B} 的情况（固定第一位为 \text{B}，剩下 n-1 位随便填），至于 dp_{n-3} 则是开头是 \text{B} 且尾部也是 \text{B} 的情况啦！显然 dp_{n-3} 包含的情况是不可接受的，因为首尾相接后就会出现连续的 \text{B}，所以要容斥减掉。

::::success[这部分的代码]

if(is_only){//纯色块
    //说明只存在 R 这一种颜色，不存在 B
    dp[0]=1,dp[1]=1;//初值即 Fibonacci 数组前两项
    for(int i=2;i<=n;i++)
        dp[i]=(dp[i-1]+dp[i-2])%MOD;//常规 Fibonacci 递推公式
    LL Ans=(dp[n]+dp[n-1]-(n>=3?dp[n-3]:0)+MOD)%MOD;//求出答案
    cout<<Ans<<"\n";return 0;//解决完毕
}

::::

一般情况：S 有 \text{R} 又有 \text{B}

首先由于 n 一定是偶数，那么这里有一个很巧妙的 trick，考虑将相邻的两个值“打包”成一组，那么“打包”后 \text{B} 其实就融入进 \text{R} 的情况了（因为每次 \text{B} 只会出现一个），而 \text{R} 的个数有上限 L，此时就可以从“划分序列”的角度入手了。

不过有个问题，\text{R} 在“打包”前的上限是 L 没错，但“打包”后的上限不可能还是一样的！准确来说，这个上限会变为 L' = \lfloor \frac{L}{2} \rfloor + 1 = \lceil \frac{L}{2} \rceil，至于为什么下取整 +1 与上取整的答案是一样的，这是因为 L 一定是一个奇数（\text{R} 只能连续出现奇数个）啦！

那么问题就变成了划分序列，将长度为 \frac{n}{2} 的序列划分为若干个区间，要求每个区间的长度不超过 L'，求有多少种划分方案。这不就是爬楼梯问题的变种嘛，总共要爬 n 层且每步可以爬 1 \sim L' 层。

定义 dp_i 表示爬到第 i 层楼的方案数，答案是 dp_n。转移很简单是 dp_i = \sum_{i-k \le j \le i-1} dp_j，但这样直接做是 O(n^2) 的，能不能快一点？

这个我会！线段树维护不就行了！呃，线段树确实可以做，但是未免太大材小用了……其实这里从“扩散型”转移考虑会更舒服，换句话说，用 dp_i 更新所有 dp_j(i+1 \le j \le i+k)，区间修改，不还是线段树吗，不对其实可以用树状数组，可以用差分 O(1) 维护嘛！这可比什么线段树啊树状数组啊跑的快多了哼。

::::success[这部分的代码]

if(n&1){cout<<"0\n";return 0;}//n 必须是偶数
n/=2,L=L/2+1;//数值两两“打包”
for(int i=1;i<=L;i++)
    dp[i]=2*i;//初值，表示链展开为环的答案
for(int i=1;i<=n;i++){
    c[i]=(c[i]+c[i-1])%MOD;//继承差分数组
    dp[i]=(dp[i]+c[i])%MOD;//更新 DP 数组
    c[i+1]=(c[i+1]+dp[i])%MOD;//维护差分数组（左端点）
    if(i+L+1<=n)//小心 RE
        c[i+L+1]=(c[i+L+1]-dp[i]+MOD)%MOD;//维护差分数组（右端点）
}
cout<<dp[n]<<"\n";//解决完毕

::::

完整代码

前面已经零散放出了核心代码，最后再给出完整的代码喵。

::::success[完整代码]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL MOD = 1e9+7;
LL n,m2,m,L,lst[N],dp[N],c[N];
string str,s;
bool is_only=1;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read(),m2=read();
    cin>>str;str=" "+str;
    L=n;//先赋值一个足够大的
    s.resize(m2+1);
    for(int i=1;i<=m2;i++){
        if(str[i]==str[1])//与开头字符相同
            s[++m]='R';//默认为 R
        else{//与开头字符不相同
            if(!m||s[m]!='B')s[++m]='B';//新开 B 段
            is_only=0;//肯定不止一种颜色了
        }
        if(m)lst[m]=(s[m]==s[m-1]?lst[m-1]:m);
        else lst[m]=1;
        //求出当前区间的左端点（起点）
        if(m>1&&s[m]=='B'&&s[m-1]=='R'&&((m-lst[m-1])&1))
            L=min(L,m-lst[m-1]);//如果该区间合法，则更新 L 值下界
    }
    for(int i=1;i<=m;i++)if(s[i]=='B'){
        //找到第一个 B 求前半段
        L=min(L,i-1ll+(i%2));//用前半段长度更新 L 值下界
        break;//只需要第一个 B，因此找到了就 break
    }
    if(is_only){//纯色块
        //说明只存在 R 这一种颜色，不存在 B
        dp[0]=1,dp[1]=1;//初值即 Fibonacci 数组前两项
        for(int i=2;i<=n;i++)
            dp[i]=(dp[i-1]+dp[i-2])%MOD;//常规 Fibonacci 递推公式
        LL Ans=(dp[n]+dp[n-1]-(n>=3?dp[n-3]:0)+MOD)%MOD;//求出答案
        cout<<Ans<<"\n";return 0;//解决完毕
    }
    if(n&1){cout<<"0\n";return 0;}//n 必须是偶数
    n/=2,L=L/2+1;//数值两两“打包”
    for(int i=1;i<=L;i++)
        dp[i]=2*i;//初值，表示链展开为环的答案
    for(int i=1;i<=n;i++){
        c[i]=(c[i]+c[i-1])%MOD;//继承差分数组
        dp[i]=(dp[i]+c[i])%MOD;//更新 DP 数组
        c[i+1]=(c[i+1]+dp[i])%MOD;//维护差分数组（左端点）
        if(i+L+1<=n)//小心 RE
            c[i+L+1]=(c[i+L+1]-dp[i]+MOD)%MOD;//维护差分数组（右端点）
    }
    cout<<dp[n]<<"\n";//解决完毕
    return 0;
}

::::

::::success[完整代码（无注释版）]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL MOD = 1e9+7;
LL n,m2,m,L,lst[N],dp[N],c[N];
string str,s;
bool is_only=1;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read(),m2=read();
    cin>>str;str=" "+str;
    L=n;
    s.resize(m2+1);
    for(int i=1;i<=m2;i++){
        if(str[i]==str[1])s[++m]='R';
        else{
            if(!m||s[m]!='B')s[++m]='B';
            is_only=0;
        }
        if(m)lst[m]=(s[m]==s[m-1]?lst[m-1]:m);
        else lst[m]=1;
        if(m>1&&s[m]=='B'&&s[m-1]=='R'&&((m-lst[m-1])&1))
            L=min(L,m-lst[m-1]);
    }
    for(int i=1;i<=m;i++)if(s[i]=='B')
        {L=min(L,i-1ll+(i%2));break;}
    if(is_only){
        dp[0]=1,dp[1]=1;
        for(int i=2;i<=n;i++)
            dp[i]=(dp[i-1]+dp[i-2])%MOD;
        LL Ans=(dp[n]+dp[n-1]-(n>=3?dp[n-3]:0)+MOD)%MOD;
        cout<<Ans<<"\n";return 0;
    }
    if(n&1){cout<<"0\n";return 0;}
    n/=2,L=L/2+1;
    for(int i=1;i<=L;i++)dp[i]=2*i;
    for(int i=1;i<=n;i++){
        c[i]=(c[i]+c[i-1])%MOD;
        dp[i]=(dp[i]+c[i])%MOD;
        c[i+1]=(c[i+1]+dp[i])%MOD;
        if(i+L+1<=n)c[i+L+1]=(c[i+L+1]-dp[i]+MOD)%MOD;
    }
    cout<<dp[n]<<"\n";
    return 0;
}

::::

最后扔一个提交记录喵，如果觉得我展出的代码不保险的话，可以去提交记录里看代码喵。

总结

感觉属于思路非常巧妙的性质 + DP 题，其实个人感觉 DP 不是重点，重点在于你要想到从特殊情况入手，并且能分析出各种颜色情况的性质（比如 \text{R} 的个数只能是奇数、\text{B} 只能单个出现、一连串 \text{R} 的长度限制等）。有了这些性质后再“打包”转化问题为变种爬楼梯，后续的差分优化是很简单的，而且实在不行你写个线段树上去也没啥。至于最开始的令 S_1 = \text{R} 感觉是经典小 trick，没什么难度。

总之是一个好题，值得一做。

题外话：我宣称这是我目前做的黑题中最难的一道，没有之一！

这篇文章总共有将近上万字符喵（从没写过这么长的题解 /ll），如果看到这里了，能不能求求你给我点个赞喵，真的太谢谢啦喵 /xin。