满分解法（100 分）

固定恶人集合后的贡献

先假设所有恶人的位置已经确定。非恶人的实际说法没有选择余地：比较左右两侧最近恶人的距离即可，距离相同也必须说左边。固定字符与这个说法不符时，该集合不合法。

恶人本人可以任意说话。若其字符已经是 L 或 R，说法只有一种；若字符为 ?，实际说法可以任选左右，贡献因子 $2$。所以一个合法恶人集合的权重是其中 ? 恶人数目的二次幂。

相邻恶人之间的条件

设相邻两个恶人的位置为 $a<b$。中间的人都是非恶人。对位置 $x$，当

$$x-a\le b-x$$

时，他离左侧恶人更近或距离相同，必须说 L；否则必须说 R。因此区间 $(a,b)$ 的说法应当是若干个 L 后接若干个 R，分界点为 $\lfloor(a+b)/2\rfloor$。

记 $R_a$ 为严格在 $a$ 右侧的第一个固定 R 位置，不存在时记为 $n+1$。如果它落在两个恶人之间，就必须处于分界点右侧：

$$R_a>\left\lfloor\frac{a+b}{2}\right\rfloor.$$

对整数移项可得 $b\le 2R_a-a-1$。更靠后的固定 R 自然也在右半边，所以只检查第一个即可。令

$$\operatorname{lim}_a=\begin{cases} n,&R_a=n+1,\\ \min(n,2R_a-a-1),&R_a\le n. \end{cases}$$

那么第一类条件就是 $b\le\operatorname{lim}_a$。

类似地，记 $L_b$ 为严格在 $b$ 左侧的最后一个固定 L 位置，不存在时记为 $0$。它必须位于分界点及以前：

$$L_b\le\left\lfloor\frac{a+b}{2}\right\rfloor,$$

等价于 $a\ge 2L_b-b$。更早的固定 L 也会自动满足。因此，$a\to b$ 合法的充要条件为

$$a<b,\qquad b\le\operatorname{lim}_a,\qquad a\ge 2L_b-b.$$

这两个极端位置分别覆盖了区间内所有固定 R 和固定 L，问号可以按其唯一真实方向填写，所以条件既必要也充分。

动态规划与树状数组

令 $dp_i$ 表示已经选出至少一个恶人、最后一个恶人在 $i$ 时的方案权重和。若 $i$ 是第一个恶人，那么它左边的所有人只能说 R，故必须有 $L_i=0$。把这个初始方案记为指示量 $[L_i=0]$。

由上一节的转移条件，

$$dp_i=w_i\left([L_i=0]+\sum_{\substack{a<i\\i\le\operatorname{lim}_a\\a\ge 2L_i-i}}dp_a\right),$$

其中 $w_i=2$ 当 $s_i=?$，否则 $w_i=1$。

从左到右扫描 $i$。树状数组下标为前驱恶人位置 $a$，维护所有尚满足 $i\le\operatorname{lim}_a$ 的 $dp_a$。状态 $a$ 在扫描到 $\operatorname{lim}_a+1$ 时过期，届时从树状数组中删除。于是当前的求和只需查询

$$[\max(1,2L_i-i),\ i-1]$$

这一段下标的权重和。计算完 $dp_i$ 后，若它至少还能转移到 $i+1$，便加入树状数组并登记过期时刻。

最后一个恶人若在 $i$，其右边所有人只能说 L，所以右侧不能再出现固定 R，即 $R_i=n+1$。答案为所有满足该条件的 $dp_i$ 之和。

初始化允许第一个恶人在任意合法位置，转移逐个添加相邻的下一个恶人，结尾条件又保证最后一段合法，因此每个非空合法恶人序列被恰好计算一次。每个状态只加入、删除一次并进行常数次树状数组操作。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

struct Fenwick {
  int n;
  vector<int> bit;

  explicit Fenwick(int n) : n(n), bit(n + 1) {}

  void add(int x, int v) {
    if (v < 0) v += mod;
    for (; x <= n; x += x & -x) {
      bit[x] += v;
      if (bit[x] >= mod) bit[x] -= mod;
    }
  }

  int sum(int x) const {
    int res = 0;
    for (; x > 0; x -= x & -x) {
      res += bit[x];
      if (res >= mod) res -= mod;
    }
    return res;
  }

  int range_sum(int l, int r) const {
    int res = sum(r) - sum(l - 1);
    if (res < 0) res += mod;
    return res;
  }
};

void solve() {
  int n;
  string s;
  cin >> n >> s;

  vector<int> next_r(n + 2, n + 1), prev_l(n + 2);
  int pos = n + 1;
  for (int i = n; i >= 1; --i) {
    next_r[i] = pos;
    if (s[i - 1] == 'R') pos = i;
  }
  pos = 0;
  for (int i = 1; i <= n; ++i) {
    prev_l[i] = pos;
    if (s[i - 1] == 'L') pos = i;
  }

  vector<int> limit(n + 1, n);
  vector<vector<int>> expire(n + 2);
  for (int i = 1; i <= n; ++i) {
    if (next_r[i] <= n) limit[i] = min(n, 2 * next_r[i] - i - 1);
    if (limit[i] >= i + 1 && limit[i] < n) expire[limit[i] + 1].push_back(i);
  }

  vector<int> dp(n + 1);
  Fenwick fw(n);
  for (int i = 1; i <= n; ++i) {
    for (int j : expire[i]) fw.add(j, -dp[j]);
    int lower = max(1, 2 * prev_l[i] - i);
    int ways = prev_l[i] == 0;
    if (lower < i) {
      ways += fw.range_sum(lower, i - 1);
      if (ways >= mod) ways -= mod;
    }
    dp[i] = (i64)ways * (s[i - 1] == '?' ? 2 : 1) % mod;
    if (limit[i] >= i + 1) fw.add(i, dp[i]);
  }

  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (next_r[i] == n + 1) {
      ans += dp[i];
      if (ans >= mod) ans -= mod;
    }
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

所有说法均不确定（通过子任务 12–13，共 10 分）

当字符串全部由 ? 组成时，任意非空恶人位置集合都合法：非恶人的说法由最近恶人唯一确定，而每个恶人可以任选 L 或 R。

对每个位置，可以不选为恶人，贡献 $1$ 种；也可以选为恶人并任选说法，贡献 $2$ 种。所有位置独立，共有 $3^n$ 种选择，其中全都不是恶人的一种不合法。因此答案为

$$3^n-1\pmod{998244353}.$$

逐次乘 $3$ 即可，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 1;
  for (int i = 0; i < n; ++i) ans = (i64)ans * 3 % mod;
  cout << (ans - 1 + mod) % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

平方动态规划（通过子任务 1–8，共 40 分）

在 $n\le 2000$ 时，沿用“最后一个恶人”的动态规划，但可以直接枚举前驱。

预处理 $R_i$ 为 $i$ 右侧第一个固定 R 的位置，$L_i$ 为 $i$ 左侧最后一个固定 L 的位置。相邻恶人为 $a<b$ 时，中间人在 $\lfloor(a+b)/2\rfloor$ 及以前说 L，以后说 R。所以转移合法当且仅当

$$L_b\le\left\lfloor\frac{a+b}{2}\right\rfloor<R_a.$$

令 $dp_b$ 表示最后一个恶人在 $b$ 的权重和。枚举所有 $a<b$ 并检查上式；若 $L_b=0$，还加入 $b$ 作为第一个恶人的方案。最后当 $s_b=?$ 时乘 $2$。答案累加所有 $R_b=n+1$ 的状态，因为最后一个恶人右侧不能出现固定 R。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> next_r(n + 2, n + 1), prev_l(n + 2);
  int pos = n + 1;
  for (int i = n; i >= 1; --i) {
    next_r[i] = pos;
    if (s[i - 1] == 'R') pos = i;
  }
  pos = 0;
  for (int i = 1; i <= n; ++i) {
    prev_l[i] = pos;
    if (s[i - 1] == 'L') pos = i;
  }

  vector<int> dp(n + 1);
  for (int i = 1; i <= n; ++i) {
    int ways = prev_l[i] == 0;
    for (int j = 1; j < i; ++j) {
      int middle = (i + j) / 2;
      if (prev_l[i] <= middle && next_r[j] > middle) {
        ways += dp[j];
        if (ways >= mod) ways -= mod;
      }
    }
    dp[i] = (i64)ways * (s[i - 1] == '?' ? 2 : 1) % mod;
  }

  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (next_r[i] == n + 1) {
      ans += dp[i];
      if (ans >= mod) ans -= mod;
    }
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

枚举恶人集合（通过子任务 1–4，共 20 分）

在 $n\le 20$ 时，可以直接枚举每个人是否为恶人。

对每个非空身份集合，逐个检查非恶人：分别向左、向右找到最近的恶人，距离相同时取左侧，据此得到他唯一合法的说法。若某个固定 L 或 R 与该说法不同，丢弃这个集合。

集合合法时，固定说法的恶人贡献 $1$，说法为 ? 的恶人各贡献 $2$。把这些权重累加并对 $998244353$ 取模即可。

时间复杂度为 $O(n^2 2^n)$，空间复杂度为 $O(n)$。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> evil(n);
  int ans = 0;
  auto dfs = [&](auto &&self, int p) -> void {
    if (p < n) {
      evil[p] = 0;
      self(self, p + 1);
      evil[p] = 1;
      self(self, p + 1);
      return;
    }
    if (accumulate(evil.begin(), evil.end(), 0) == 0) return;
    int ways = 1;
    for (int i = 0; i < n; ++i) {
      if (evil[i]) {
        if (s[i] == '?') ways = 2 * ways % mod;
        continue;
      }
      int l = i - 1, r = i + 1;
      while (l >= 0 && !evil[l]) --l;
      while (r < n && !evil[r]) ++r;
      char said = r == n || (l >= 0 && i - l <= r - i) ? 'L' : 'R';
      if (s[i] != '?' && s[i] != said) return;
    }
    ans += ways;
    if (ans >= mod) ans -= mod;
  };
  dfs(dfs, 0);
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}