「Codeforces gym 102268K」Knowledge 题解

奥妙重重的结论题。

题目链接

顺着官方题解去找，能在 wiki 上找到一个叫「四面体空间对称群」的东西。发现有一堆意味不明的申必记号，但还是有一张人能看懂的图。

By Debivort, CC BY-SA 3.0

如果你立体几何好的话，你就会发现把其中一个旋转 \(180^\circ\) 的操作当作本题的 \(\texttt{a}\)，把其中一个旋转 \(120^\circ\) 的操作当作本题的 \(\texttt{b}\)，就是本题在干的事：（以下叙述以左上角的 \(180^\circ\) 旋转为 \(\texttt{a}\)，以绕 \(z\) 轴旋转 \(120^\circ\) 为 \(\texttt{b}\)）

\(\texttt{aa}\) 和 \(\texttt{bbb}\) 显然是转回去了，模拟一下 \(\texttt{ababab}\) 也会转回去，也就是说同一个等价类可以任意加入/删除这三个字符串，这是和我们的要求等价的！

同时这两个操作是可以组合成任意一种图中的操作的，手动模拟一下就能发现（以右上角开始顺时针描述各个四面体的状态，分别为：\(\texttt{a},\texttt{babb},\texttt{bbab},\texttt{ab},\texttt{bb},\texttt{bab},\texttt{abb},\texttt{ba},\texttt{aba},\texttt{b},\texttt{bba}\)，还有正中间的状态为 \(\varnothing\)）。

然后就找一下每个等价类加上 \(\texttt{a}\) 和 \(\texttt{b}\) 会转移到哪个等价类，做一遍矩阵快速幂，就能得到长度为 \(n\) 的字符串中每个等价类的大小。

const int N = 12;
const int Mod = 998244353;
// 0     1  2  3   4   5   6    7    8    9    10    11
// null  a  b  ab  ba  bb  aba  abb  bab  bba  babb  bbab

const int tran[N][2] = {{1, 2}, {0, 3}, {4, 5},  {6, 7},  {2, 8},  {9, 0},
                        {3, 9}, {8, 1}, {7, 10}, {5, 11}, {11, 4}, {10, 6}};

class Matrix {
 public:
  int a[N][N];
  friend Matrix operator*(const Matrix &a, const Matrix &b);
  friend Matrix operator^(Matrix a, int b);
  Matrix() { memset(a, 0, sizeof(a)); }
};

int main() {
  int n;
  scanf("%d", &n);
  int now = 0;
  for (int i = 1; i <= n; ++i) {
    char c = getchar();
    while (!isalpha(c))
      c = getchar();
    if (c == 'a')
      now = tran[now][0];
    else
      now = tran[now][1];
  }
  int x;
  scanf("%d", &x);
  Matrix a;
  for (int i = 0; i < N; ++i)
    ++a.a[i][tran[i][0]], ++a.a[i][tran[i][1]];
  Matrix ans;
  ans = a ^ x;
  printf("%d\n", ans.a[0][now]);
  return 0;
}

Matrix operator*(const Matrix &a, const Matrix &b) {
  Matrix ans;
  for (int i = 0; i < N; ++i) {
    for (int k = 0; k < N; ++k) {
      for (int j = 0; j < N; ++j) {
        ans.a[i][j] = (ans.a[i][j] + 1ll * a.a[i][k] * b.a[k][j]) % Mod;
      }
    }
  }
  return ans;
}
Matrix operator^(Matrix a, int b) {
  Matrix ans;
  for (int i = 0; i < N; ++i)
    ans.a[i][i] = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}