题解：P14256 平局（draw）

wzj33300 · 2025-10-18 19:35:01 · 题解

验题人题解。

以下讨论都在模 3 意义下进行。

约定石头为 2，剪刀为 1，布为 0，即 x 击败 (x-1)。

两个观察：

1. 如果出现两个相同的手势，则可以直接消去一个。

2. 如果出现形如 x,x-1,x 的情况，则可以替换成一个 x。

   证明考虑如果要让中间的 x-1 对答案有贡献，则左右两边的 x 必须损失一个，答案不会变大。

把这两种情况全部消去，剩下的数必定形如：

考虑在 x 前面有 a 项，x 后面有 b 项，则答案为 \left \lfloor \frac a3 \right \rfloor + \left \lfloor \frac b3 \right \rfloor + \left [ a\equiv b\equiv 2 \pmod{3} \right ] ，容易手模出来。

现在我们再观察前面的两种情况，如果我们已经知道前 i 个人的 a,b 值，考虑下一个人：

1. 相当于直接消去，对 a,b 无影响。
2. 让 b\gets b-1。

于是我们就可以直接 dp 了。设当前考虑到 i，第 i 个人的选择出 x，当前的 a 和 b。考虑下一个人出 x'：

每当发生消去时，答案要额外 +1，记录方案数和当前的答案，即可做到 O(n^3)。注意到 a 不降，于是只用记录 a \bmod 3 即可，时间复杂度 O(n^2)。

:::info[代码]

constexpr int N = 3005;
char s[N];
Mint f[N][3][N][3], g[N][3][N][3];
vi possible[N];

// signed main() {
int main() {
  // freopen("draw3.in", "r", stdin);
  // freopen(".out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  cin >> reinterpret_cast<char (&)[N]>(s[1]);
  for (int i = 1; i <= n; i++) s[i] -= '0';
  for (int i = 1; i <= n; i++) {
    for (auto j : {0, 1, 2})
      if (s[i] >> j & 1) possible[i].pb(j);
  }
  for (auto x : possible[1]) g[1][0][0][x] = 1;
  for (int i = 1; i < n; i++) {
    for (auto x : possible[i]) {
      for (int upl = 0; upl < 3; upl++) {
        for (int downl = 0; downl < i; downl++) {
          auto &F = f[i][upl][downl][x], &G = g[i][upl][downl][x];
          if (F != 0 || G != 0) {
            for (auto nx : possible[i + 1]) {
              if (x == nx) {
                g[i + 1][upl][downl][nx] += G;
                f[i + 1][upl][downl][nx] += F + G;
              } else if ((x + 1) % 3 == nx) {
                if (downl == 0) {
                  g[i + 1][(upl + 1) % 3][downl][nx] += G;
                  f[i + 1][(upl + 1) % 3][downl][nx] += F + G * (upl == 2);
                } else {
                  g[i + 1][upl][downl - 1][nx] += G;
                  f[i + 1][upl][downl - 1][nx] += F + G;
                }
              } else {
                g[i + 1][upl][downl + 1][nx] += G;
                f[i + 1][upl][downl + 1][nx] += F;
              }
            }
          }
        }
      }
    }
  }
  Mint ans = 0;
  for (auto x : possible[n]) {
    for (int upl = 0; upl < 3; upl++) {
      for (int downl = 0; downl < n; downl++) {
        auto &F = f[n][upl][downl][x], &G = g[n][upl][downl][x];
        ans += F + G * (downl / 3 + (upl == 2 && downl % 3 == 2));
      }
    }
  }
  cout << ans << endl;

  return 0;
}

:::