AGC050C 题解

joke3579 · 2022-11-17 17:52:02 · 题解

\text{statement}

有一个由房间组成的序列，其向左右两端无限延伸。你和 Snuke 在玩下面的游戏：

裁判给出一个由 B 和 S 组成的字符串 t，名为回合决定串，并将它展示给两名玩家。
首先，Snuke 站在其中一个房间里。
随后，对于每个 i = 1,2,\dots,|t|，发生如下的事件：
- 如果 t 中第 i 个字母为 B，则这是你的回合。你会选择一个其中没有障碍或 Snuke 的房间，在其中放置一个障碍。这之后，如果 Snuke 所在房间左右两侧的房间均放置有障碍，则你胜利，游戏结束。
- 如果 t 中第 i 个字母为 S，则这是 Snuke 的回合。他可以移动到与当前所在房间相邻且无障碍的房间，或什么都不做。
如果 |t| 轮后游戏仍未结束，则 Snuke 胜利，游戏结束。

给定字符串 s，其中仅含有 B、S 与 ? 三种字符。设 s 中含有 q 个 ?，有 2^q 种填法将 s 中的 ? 替换为 B 或 S，得到一个回合决定串。假设两名玩家都按最优策略操作，在这 2^q 个串中，有多少种填法使得你能胜利呢？

请输出答案模 998244353 的值。

## $\text{solution}

记 (L,R) 为 Snuke 可能面对的一个局面，其中 L 为 Snuke 向左可以走入的房间数，R 为 Snuke 向右可以走入的房间数。有 (L,R) 等价于 (R,L)。

容易发现你操作的最优策略是将 Snuke 的一侧堵死，令其在这一侧可以走入的房间数为 0。重新陈述游戏：
Snuke 的初始局面为 (\infty, \infty)。在 Snuke 的回合，他可以将 (L,R) 的局面转移为 (L\pm 1, R\mp 1) 或不变。在你的回合，你会将 (L,R) 的局面转移为 (\min\{L,R\},0)。

可以发现，你进行的每次操作都会至少将 Snuke 的可达范围缩小至原来的二分之一。因此你只需要操作 O(\log |s|) 次就可以胜利。
这个条件不好计数你胜利的串，但便于计数 Snuke 胜利的串。考虑首先求得在这 2^q 个串中 Snuke 胜利的串的数量，再用 2^q 减去其就是答案。

考虑倒序枚举。我们发现，当位置 i 的字符为 B 且其为倒数第 k 个时，必须保证 i 到下一个 B 之间存在至少 2^{k-1} 个 S。只有这样才能使得 Snuke 在当前情况下不败。
这引出了 dp 的解法。

由于 dp 方程的第二维取值范围为 O(\log n)，总时间复杂度 O(n\log n)。

\text{code : }

#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
const int N = 1e6 + 10, mod = 998244353;
int add(int a, int b) { return (a += b) >= mod ? a - mod : a; }
int n, ans = 1, lgv, f[N][24], cnt[N], len;
char s[N];

signed main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> s + 1; n = strlen(s + 1), lgv = __lg(n) + 1;
    reverse(s + 1, s + 1 + n);
    rep(i,1,n) {
        if (s[i] == 'B') cnt[i + 1] = cnt[i] + 1;
        else cnt[i + 1] = cnt[i];
        if (s[i] == '?') ans = add(ans, ans);
    } f[0][0] = 1;
    rep(i,1,n) {
        if (s[i] == 'S' or s[i] == '?') {
            memcpy(f[i], f[i - 1], sizeof f[i]);
        }
        if (s[i] == 'B' or s[i] == '?') {
            rep(j,1,lgv) {
                len = 0; if (j > 1) len = 1 << j - 2;
                int from = max(0, i - len - 1); len = min(len, i);
                if (len == 0 or cnt[i] == cnt[i - len]) 
                    f[i][j] = add(f[i][j], f[from][j - 1]);
            }
        } 
    } 
    rep(i,0,lgv) ans = add(ans, mod - f[n][i]);
    cout << ans << '\n';
}