「Codeforces Gym 102268K」Knowledge

题目链接:Codeforces Gym 102268K

你有一个长度为 $n$ 的字符串,只包含小写字母 ab

你可以进行任意次(包括 $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$,ab 分别表示对这个正四面体的两种操作。a 表示沿 $EF$($E, F$ 分别表示 $AB, CD$ 的中点)轴旋转 $180 ^ {\circ}$,b 表示沿 $z$ 轴旋转 $120 ^ {\circ}$。可以发现 aabbbababab 均可以使正四面体回到初始状态(即同一等价类)。那么等价类个数即为正四面体的置换群大小

Orz hehezhou 随手证明!

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

那么问题变为:对于一个空串,不断往后面加入 ab 直到长度为 $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;
}

1 条评论

  1. 惠州注册公司

    又发现一个好站,收藏了~以后会经常光顾的 (。•ˇ‸ˇ•。)

发表评论