T2AT4928 [AGC033E] Go around a Circle
有一个圆，圆弧被 N 个点分成了等长的 N 段，每段被染成了红色或蓝色。给定一个长为 M 的只包含 R 和 B 的字符串 S，R 代表红色，B 代表蓝色。
求出有多少种给圆弧染色的方案，满足将棋子放在任意一个点上，都存在一种进行 M 次操作的方案，每次操作选择将棋子顺时针或逆时针移动一段，使得第 i 此经过的段的颜色为 S_i。
答案对 10^9+7 取模。
如果两种方案旋转后相同，它们视作不同的方案。
n <= 2e5
假定第一个字符是R
先考虑，若这个S都是一种颜色，那么问题就变成了，在一个圆环上染色，其中B不能出现连续，将RRRB这种看作一段，那么就是相当于用若干个长度>=2的段填充这个圆。由于是个圆不太好弄，可以枚举第一段的长度，然后变成序列上的问题，再将贡献乘上第一段的长度(表示可以移动这么多的长度)。
对于普遍情况而言，
由于第一个是R，所以不能有连续的两个及两个以上的B，并且圆环上的R长度必须为奇数，还有，R的长度不能超过序列上所有 极长R的 奇数的长度 的最小值。 就是说把序列上所有极长的R都拿出来，再去掉所有长度为偶数的，去剩下的所有的长度的最小值。
为啥？
不能有连续的B，
是因为第一个R,如果选择从两个B中间的点出发，就不可能让第一个字符是R。
圆环上长度必须是奇数。
如果是偶数的话会有不能到的点 ， (比如，一个长度为4的圆环，不能保证所有的点都能走3步到达两端)；
最后，长度问题。
因为序列上的一段R肯定都是从圆环上的一个B的边的两边开始的。
若是一个偶数的R段，那么可以来回走，一直在起点和第一个点之间往返。（它不会一去不返，因为R段长都是奇数，走偶数步不可能到端点）；
若是奇数的话，只能一直往一个方向走，为了保证从所有点开始都能走出去，它肯定要小于等于最小的长度。
若最小的长度为K
同样把B加上去，那么长度就是 2 ~ K + 1 之间的偶数。
所以，最后问题就转化成了，用一堆长度为 2 ~ K+1 的偶数拼成一个圆环的方案数。
同样枚举第一个段的长度，计算即可。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 2e5+10 , mod = 1e9+7;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , m;
char s[N];
int sum[N] , f[N];
int main()
{
n = read(); m = read(); scanf("%s" , s+1);
int i , mx , ans = 0;
for(i = 1 ; i <= m ; ++i) if(s[i] != s[1]) break;
mx = i - 1;
if(mx == m)
{
sum[0] = f[0] = ans = 1;
for(int i = 1 ; i <= n ; ++i)
{
if(i >= 2) f[i] = sum[i-2];
sum[i] = (sum[i-1] + f[i]) % mod;
}
for(int i = 0 ; n - i >= 2 ; ++i) (ans += (LL)f[i] * (n - i) % mod) %= mod;
cout << ans << '
'; return 0;
}
if(n & 1) return puts("0") , 0;
if(mx % 2 == 0) mx++;
for(int tmp = 0 ; i <= m ; ++i)
{
if(s[i] == s[1]) tmp++;
else
{
if(tmp & 1) mx = min(mx , tmp);
tmp = 0;
}
}
mx = (mx + 1) >> 1; n >>= 1; f[0] = sum[0] = 1;
for(int i = 1 ; i <= n ; ++i)
{
f[i] = (sum[i-1] - (i - mx - 1 >= 0 ? sum[i - mx - 1] : 0) + mod) % mod;
sum[i] = (sum[i-1] + f[i]) % mod;
}
for(int i = 0 ; i <= n ; ++i) if(n - i <= mx) (ans += (LL)f[i] * (n - i) % mod * 2 % mod) %= mod;
cout << ans << '
'; return 0;
}
好累啊。。。