题目链接：Codeforces Gym 102268 K

你有一个长度为 $n$ 的字符串，只包含小写字母 a 和 b。

你可以进行任意次（包括 $0$ 次）如下操作：

• 从字符串任意位置删除子串 aa。
• 从字符串任意位置删除子串 bbb。
• 从字符串任意位置删除子串 ababab。
• 在字符串任意位置插入子串 aa。
• 在字符串任意位置插入子串 bb。
• 在字符串任意位置插入子串 ababab。

请求出最终能得到多少本质不同的长度为 $x$ 的字符串。答案对 $998244353$ 取模。

数据范围：$1 \le n \le 3 \times 10 ^ {5}$，$0 \le x \le 10 ^ {9}$。

Solution

记字符串 $s$ 经过任意次操作后可以达到的最短的字符串为 $f(s)$。打表可以发现只有 $12$ 种 $f(s)$。具体如下：

(∅)
a
b
ab
ba
bb
aba
abb
bab
bba
babb
bbab

可以采用几何方法证明：对于一个正四面体 $ABCD$，a 和 b 分别表示对这个正四面体的两种操作。a 表示沿 $EF$（$E, F$ 分别表示 $AB, CD$ 的中点）轴旋转 $180 ^ {\circ}$，b 表示沿 $z$ 轴旋转 $120 ^ {\circ}$。可以发现 aa，bbb 和 ababab 均可以使正四面体回到初始状态（即同一等价类）。那么等价类个数即为正四面体的置换群大小。

Orz hehezhou 随手证明！

即所有字符串被划分为 $12$ 个等价类，等价类内的字符串都可以通过 $6$ 种操作相互得到。对于一个字符串 $s$，可以发现 $s + \text{a}$ 一定转移到另一个等价类，$s + \text{b}$ 也转移到另一个等价类中（这本质上是一个自动机）。

那么问题变为：对于一个空串，不断往后面加入 a 或 b 直到长度为 $x$，求与原字符串 $s$ 在同一个等价类内的字符串个数。

可以预处理出等价类之间的转移，使用矩阵乘法计算答案。

时间复杂度：$\mathcal O(n + 12 ^ {3} \log x)$。

Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 12, MOD = 998244353;
int tot;
std::map<std::string, int> map;
std::map<std::string, std::string> trans;
std::string pat[N];

inline void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
struct Matrix {
    int A[N][N];
    inline Matrix() {
        memset(A, 0, sizeof(A));
    }
    inline void identity() {
        for (int i = 0; i < N; i++) {
            A[i][i] = 1;
        }
    }
    inline int *operator[](int x) {
        return A[x];
    }
    inline const int *operator[](int x) const {
        return A[x];
    }
    inline Matrix operator*(const Matrix &rhs) const {
        Matrix ans;
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                int r = A[i][k];
                for (int j = 0; j < N; j++) {
                    add(ans[i][j], (int64)r * rhs[k][j] % MOD);
                }
            }
        }
        return ans;
    }
    inline Matrix operator^(int k) const {
        Matrix x = *this, ans;
        ans.identity();
        for (; k > 0; k >>= 1, x = x * x) {
            if (k & 1) {
                ans = ans * x;
            }
        }
        return ans;
    }
};

inline void insert(const std::string &str) {
    pat[map[str] = tot++] = str;
}
inline int match(const std::string &str) {
    std::string t;
    for (auto x : str) {
        t += x;
        if (trans.count(t)) {
            t = trans[t];
        }
    }
    return map[t];
}
int main() {
    std::string str;
    int n, l;
    std::cin >> n >> str >> l;
    insert("");
    insert("a");
    insert("b");
    insert("ab");
    insert("ba");
    insert("bb");
    insert("aba");
    insert("abb");
    insert("bab");
    insert("bba");
    insert("babb");
    insert("bbab");
    trans["aa"] = "";
    trans["baa"] = "b";
    trans["bbb"] = "";
    trans["abaa"] = "ab";
    trans["abab"] = "bba";
    trans["abba"] = "bab";
    trans["abbb"] = "a";
    trans["baba"] = "abb";
    trans["bbaa"] = "bb";
    trans["babba"] = "bbab";
    trans["babbb"] = "ba";
    trans["bbaba"] = "babb";
    trans["bbabb"] = "aba";
    Matrix A;
    for (int i = 0; i < N; i++) {
        A[match(pat[i] + "a")][i]++;
        A[match(pat[i] + "b")][i]++;
    }
    A = A ^ l;
    printf("%d\n", A[match(str)][match("")]);
    return 0;
}