题解：P14256 平局（draw）

· · 题解

容易想到大概率需要从左往右扫描，然后用一些 dp of dp 或者贪心 of dp 之类的做。

感受一下，这里大概率应该是贪心 of dp。下面记 \mathtt {A,B,C} 分别为剪刀、石头、布，用 s 表示整个字母串。

先把所有相邻相同的字母消除掉，然后发现我们其实是不断这样操作：选择两个相同的字母 s_i, s_j，比如都为 \mathtt B，并且 s_{i + 1}, s_{i + 2}, \dots, s_{j - 1} 中至少存在一个 \mathtt A，那么可以将 s_i, s_{i + 1}, \dots, s_j 合并成一个 \mathtt B。我们需要求解的是操作次数的最大值。

首先我们观察：若存在形如 \mathtt {BAB} 的子串，那么直接操作这两个 \mathtt B 一定不劣。如果不操作，说明中间的 \mathtt A 有用，这与放弃中间的 \mathtt A 的操作转而对旁边两个 \mathtt B 操作的答案相等。

剩下的只需要考虑 \mathtt {ABA} 以及其他情况。

如果不存在形如 \mathtt {ABA} 这样的形式，那么整个串可以用 \mathtt {ABC} 或 \mathtt {ACB} 的循环表示。设 f_{i, j, c, 0/1} 表示依次加入了字母 s_1, s_2, \dots, s_i 后，当前串由形如 \mathtt {ABC/ACB} 循环构成，长度为 j，且最后一个字母为 c 的方案数。

这就产生了新的状态：形如 \mathtt {\dots ABCABCABCABA} 这样的串，不妨用 f_{i, j, c, 2} 表示这样的状态，其中需要满足 j\ge 4（形如 \mathtt {ABA} 这样的串会在下面归为 f_{i, j, c, 3}）。

那么我们考虑 f_{i, j, c, 2} 在加入一个新字母 s_{i + 1} 后该如何转移，不妨令当前串为 \mathtt {\dots ABCABCABA}。

最后我们考虑 f_{i, j, c, 3} 加入一个字母 s_{i + 1} 后如何转移，不妨令当前串为 \mathtt {ABACBACB \dots ACBACBA}。

加入完所有字母后，对最终得到的串不断进行操作直到不能操作为止。对于 f_{n, j, c, 0/1} 贡献为 \lfloor \frac {j - 1} 3 \rfloor，对于 f_{n, j, c, 2 / 3} 贡献为 \lfloor \frac {j - 2} 3 \rfloor。总时间复杂度为 \mathcal O(n ^ 2)。

#include <bits/stdc++.h>
#define ll int
#define LL long long
#define uLL unsigned LL
#define fi first
#define se second
#define mkp make_pair
#define pir pair<ll, ll>
#define pb push_back
#define i128 __int128
using namespace std;
char buf[1 << 22], *p1, *p2;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF :
// *p1++)
template <class T>
const inline void rd(T &x) {
    char ch;
    bool neg = 0;
    while (!isdigit(ch = getchar()))
        if (ch == '-')
            neg = 1;
    x = ch - '0';
    while (isdigit(ch = getchar())) x = (x << 1) + (x << 3) + ch - '0';
    if (neg)
        x = -x;
}
const ll maxn = 3010, mod = 1e9 + 7, inf = 1e9;
ll power(ll a, ll b = mod - 2, ll p = mod) {
    ll s = 1;
    while (b) {
        if (b & 1)
            s = 1ll * s * a % p;
        a = 1ll * a * a % p, b >>= 1;
    }
    return s;
}
template <class T, class _T>
const inline ll pls(const T x, const _T y) { return x + y >= mod ? x + y - mod : x + y; }
template <class T, class _T>
const inline ll mus(const T x, const _T y) { return x < y ? x + mod - y : x - y; }
template <class T, class _T>
const inline void add(T &x, const _T y) { x = x + y >= mod ? x + y - mod : x + y; }
template <class T, class _T>
const inline void sub(T &x, const _T y) { x = x < y ? x + mod - y : x - y; }
template <class T, class _T>
const inline void chkmax(T &x, const _T y) { x = x < y ? y : x; }
template <class T, class _T>
const inline void chkmin(T &x, const _T y) { x = x < y ? x : y; }

ll n, a[maxn], f[maxn][maxn][3][4], suf[maxn], ans;
char str[maxn];

int main() {
    rd(n), scanf("%s", str + 1);
    for(ll i = 1; i <= n; i++) a[i] = str[i] - '0';
    for(ll c = 0; c < 3; c++)
        if(a[1] & (1 << c)) f[1][1][c][0] = 1;
    suf[n + 1] = 1;
    for(ll i = n; i; i--)
        suf[i] = 1ll * suf[i + 1] * __builtin_popcount(a[i]) %mod;
    for(ll i = 2; i <= n; i++) {
        for(ll j = 1; j < i; j++)
            for(ll p = 0; p < 3; p++)
                for(ll u = 0; u < 4; u++)
                    for(ll q = 0; q < 3; q++) {
                        if(!(a[i] & (1 << q)) || !f[i - 1][j][p][u]) continue;
                        if(p == q) {
                            add(ans, 1ll * f[i - 1][j][q][u] * suf[i + 1] %mod);
                            add(f[i][j][q][u], f[i - 1][j][p][u]);
                        } else {
                            ll z = (q == (p + 1) % 3);
                            if(u == 2) {
                                if(z) {
                                    add(ans, 1ll * f[i - 1][j][p][2] * suf[i + 1] %mod);
                                    add(f[i][j - 1][q][0], f[i - 1][j][p][2]);
                                } else {
                                    add(ans, (j - 2) / 3 * 1ll * f[i - 1][j][p][2] %mod * suf[i + 1] %mod);
                                    if(j % 3 == 0) add(f[i][4][q][3], f[i - 1][j][p][2]);
                                    else if(j % 3 == 1) add(f[i][4][q][1], f[i - 1][j][p][2]);
                                    else add(f[i][3][q][1], f[i - 1][j][p][2]);
                                }
                            }
                            if(u == 3) {
                                if(z) {
                                    add(ans, 1ll * f[i - 1][j][p][3] * suf[i + 1] %mod);
                                    if(j == 3) add(f[i][2][q][0], f[i - 1][j][p][3]);
                                    else add(f[i][j - 1][q][3], f[i - 1][j][p][3]);
                                } else add(f[i][j + 1][q][3], f[i - 1][j][p][3]);
                            }
                            if(u == 0) {
                                if(z) add(f[i][j + 1][q][0], f[i - 1][j][p][0]);
                                else {
                                    if(j == 1) add(f[i][j + 1][q][1], f[i - 1][j][p][0]);
                                    else if(j == 2) add(f[i][3][q][3], f[i - 1][j][p][0]);
                                    else add(f[i][j + 1][q][2], f[i - 1][j][p][0]);
                                }
                            }
                            if(u == 1) {
                                if(z) {
                                    add(ans, 1ll * f[i - 1][j][p][1] * suf[i + 1] %mod);
                                    add(f[i][j - 1][q][j > 2], f[i - 1][j][p][1]);
                                } else add(f[i][j + 1][q][1], f[i - 1][j][p][1]);
                            }
                        }
                    }
    }
    for(ll i = 1; i <= n; i++)
        for(ll c = 0; c < 3; c++) {
            add(ans, (i - 1) / 3 * 1ll * (f[n][i][c][0] + f[n][i][c][1]) %mod);
            add(ans, (i - 2) / 3 * 1ll * (f[n][i][c][2] + f[n][i][c][3]) %mod);
        }
    printf("%d\n", ans);
    return 0;
}