Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the biology story for a second. Insert/delete operations are just relations: AA, BBB, and s are all equal to the empty string.
Because AA = empty and BBB = empty, both letters are invertible: A^{-1}=A and B^{-1}=BB. So we are counting words in the group G = <A,B | A^2 = B^3 = s = 1>.
Once you have the Cayley graph of this group, the problem becomes boring in the best way: each length-n string is a walk of length n choosing edge A or edge B.
The scary-looking group is tiny here. Since s starts with A, ends with B, has no AA and no BBB, it is made of blocks AB and ABB. With length at most 11, there are only 35 possible presentations, and the largest resulting group has 60 elements.
Build the Cayley graph with a Todd-Coxeter-style table. Enforce every relator from every state; a contradiction merges states, one missing edge is forced, and otherwise you create one new state. Then matrix-exponentiate the two-letter transition matrix.
The trap is thinking this is a string-reduction problem. It is not. Greedily deleting AA, BBB, or s is cute, but insertions can create new deletions somewhere else, so local reduction alone gets absolutely cooked.
Turn Mutations Into Algebra
Write the two letters as generators A and B. The allowed operations say , , and .
So all strings live in the group .
This is not just a metaphor. The quotient by these relations is already a group, because A is its own inverse and B^{-1}=BB. Therefore two gene strings are mutually reachable exactly when they represent the same element of .
So the problem becomes: find the group element represented by t; among all binary strings of length , count how many represent that same element.
If we know the Cayley graph of with edges labeled A and B, then every length- string is exactly a length- walk starting at the identity. We just need the number of walks ending at value(t).
Why The Group Is Small Enough
The constraints on s are doing a ton of work. Since s starts with A, ends with B, has no AA, and has no BBB, it must be a concatenation of blocks AB and ABB. Its total length is at most , so there are only possible strings s.
For all of them, the quotient group is finite; the largest case is ABABABABAB, giving elements. The solution below does not hardcode those cases. It builds the finite group table at runtime.
Todd-Coxeter Table
Use three internal generator columns: 0 for multiplying by A, 1 for multiplying by B, and 2 for multiplying by B^{-1}. Their inverse columns are {0,2,1}.
A table row is a group element. table[x][g] = y means multiplying element x by generator g gives element y.
We enforce the relators AA, BBB, s, s^{-1}, and all cyclic rotations of them. Cyclic rotations are not required in theory, but they make propagation much stronger and keep the code fast.
For each current row c and relator , we need . Scan known edges from the left side of , and known inverse edges from the right side.
Three things can happen:
If a full pass gives no forced edge or merge, but some table entry is still undefined, create a new row for the smallest undefined edge. Repeat.
This is coset enumeration for the trivial subgroup, meaning the finished rows are the actual group elements. Once the table is complete, we have the Cayley graph.
Counting Walks
Let . Build an matrix where .
That counts one step of choosing either A or B.
Start with vector , where state 0 is the identity. Then contains the number of length- strings producing every group element. Compute target = value(t) by walking through the Cayley table using letters of t, and output the target coordinate.
Complexity per test case is with . Once the group table exists, the rest is basically a victory lap.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const ll MOD = 998244353;
struct ToddCoxeter {
vector<vector<int>> rels;
vector<array<int, 3>> tab;
vector<int> parent;
int inv[3] = {0, 2, 1};
ToddCoxeter(vector<vector<int>> rels_) : rels(move(rels_)) {
newCoset();
}
int newCoset() {
int id = (int)parent.size();
parent.push_back(id);
array<int, 3> row;
row.fill(-1);
tab.push_back(row);
return id;
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (b < a) swap(a, b);
parent[b] = a;
for (int g = 0; g < 3; g++) {
int x = tab[a][g], y = tab[b][g];
if (x == -1 && y != -1) tab[a][g] = y;
else if (x != -1 && y != -1) unite(x, y);
}
return true;
}
bool defineEdge(int a, int g, int b) {
bool changed = false;
a = find(a);
b = find(b);
int x = tab[a][g];
if (x == -1) {
tab[a][g] = b;
changed = true;
} else if (find(x) != b) {
changed |= unite(x, b);
}
a = find(a);
b = find(b);
int rg = inv[g];
int y = tab[b][rg];
if (y == -1) {
tab[b][rg] = a;
changed = true;
} else if (find(y) != a) {
changed |= unite(y, a);
}
return changed;
}
void compress() {
for (int i = 0; i < (int)parent.size(); i++) parent[i] = find(i);
for (int i = 0; i < (int)parent.size(); i++) {
if (parent[i] != i) continue;
for (int g = 0; g < 3; g++) {
if (tab[i][g] != -1) tab[i][g] = find(tab[i][g]);
}
}
}
bool scanOnce() {
bool changed = false;
compress();
int rows = (int)parent.size();
for (int c = 0; c < rows; c++) {
if (find(c) != c) continue;
for (const auto &r : rels) {
int len = (int)r.size();
int l = 0, left = c;
while (l < len) {
left = find(left);
int nxt = tab[left][r[l]];
if (nxt == -1) break;
left = find(nxt);
l++;
}
int rr = len, right = c;
while (rr > l) {
right = find(right);
int nxt = tab[right][inv[r[rr - 1]]];
if (nxt == -1) break;
right = find(nxt);
rr--;
}
if (rr == l) {
if (find(left) != find(right)) changed |= unite(left, right);
} else if (rr == l + 1) {
changed |= defineEdge(left, r[l], right);
}
}
}
return changed;
}
vector<array<int, 3>> run() {
while (true) {
while (scanOnce()) {}
compress();
int row = -1, gen = -1;
for (int i = 0; i < (int)parent.size() && row == -1; i++) {
if (find(i) != i) continue;
for (int g = 0; g < 3; g++) {
if (tab[i][g] == -1) {
row = i;
gen = g;
break;
}
}
}
if (row == -1) break;
defineEdge(row, gen, newCoset());
}
compress();
vector<int> reps, id(parent.size(), -1);
for (int i = 0; i < (int)parent.size(); i++) {
if (find(i) == i) {
id[i] = (int)reps.size();
reps.push_back(i);
}
}
vector<array<int, 3>> res(reps.size());
for (int i = 0; i < (int)reps.size(); i++) {
int r = reps[i];
for (int g = 0; g < 3; g++) res[i][g] = id[find(tab[r][g])];
}
return res;
}
};
vector<vector<int>> makeRelators(const string &s) {
vector<vector<int>> base;
base.push_back({0, 0});
base.push_back({1, 1, 1});
vector<int> w;
for (char c : s) w.push_back(c == 'A' ? 0 : 1);
base.push_back(w);
vector<int> iw;
for (int i = (int)w.size() - 1; i >= 0; i--) iw.push_back(w[i] == 0 ? 0 : 2);
base.push_back(iw);
set<vector<int>> seen;
vector<vector<int>> rels;
for (const auto &r : base) {
int len = (int)r.size();
for (int shift = 0; shift < len; shift++) {
vector<int> cur;
for (int i = 0; i < len; i++) cur.push_back(r[(shift + i) % len]);
if (seen.insert(cur).second) rels.push_back(cur);
}
}
return rels;
}
using Mat = vector<vector<ll>>;
Mat mulMat(const Mat &a, const Mat &b) {
int n = (int)a.size();
Mat c(n, vector<ll>(n, 0));
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) if (a[i][k]) {
for (int j = 0; j < n; j++) if (b[k][j]) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}
vector<ll> mulVec(const vector<ll> &v, const Mat &m) {
int n = (int)v.size();
vector<ll> res(n, 0);
for (int i = 0; i < n; i++) if (v[i]) {
for (int j = 0; j < n; j++) if (m[i][j]) {
res[j] = (res[j] + v[i] * m[i][j]) % MOD;
}
}
return res;
}
int main() {
setIO();
int q;
cin >> q;
while (q--) {
string s, t;
ll n;
cin >> s >> t >> n;
ToddCoxeter tc(makeRelators(s));
auto trans = tc.run();
int m = (int)trans.size();
int target = 0;
for (char c : t) target = trans[target][c == 'A' ? 0 : 1];
Mat mat(m, vector<ll>(m, 0));
for (int i = 0; i < m; i++) {
mat[i][trans[i][0]]++;
mat[i][trans[i][1]]++;
}
vector<ll> vec(m, 0);
vec[0] = 1;
while (n > 0) {
if (n & 1) vec = mulVec(vec, mat);
mat = mulMat(mat, mat);
n >>= 1;
}
cout << vec[target] % MOD << char(10);
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const ll MOD = 998244353;
struct ToddCoxeter {
vector<vector<int>> rels;
vector<array<int, 3>> tab;
vector<int> parent;
int inv[3] = {0, 2, 1};
ToddCoxeter(vector<vector<int>> rels_) : rels(move(rels_)) {
newCoset();
}
int newCoset() {
int id = (int)parent.size();
parent.push_back(id);
array<int, 3> row;
row.fill(-1);
tab.push_back(row);
return id;
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (b < a) swap(a, b);
parent[b] = a;
for (int g = 0; g < 3; g++) {
int x = tab[a][g], y = tab[b][g];
if (x == -1 && y != -1) tab[a][g] = y;
else if (x != -1 && y != -1) unite(x, y);
}
return true;
}
bool defineEdge(int a, int g, int b) {
bool changed = false;
a = find(a);
b = find(b);
int x = tab[a][g];
if (x == -1) {
tab[a][g] = b;
changed = true;
} else if (find(x) != b) {
changed |= unite(x, b);
}
a = find(a);
b = find(b);
int rg = inv[g];
int y = tab[b][rg];
if (y == -1) {
tab[b][rg] = a;
changed = true;
} else if (find(y) != a) {
changed |= unite(y, a);
}
return changed;
}
void compress() {
for (int i = 0; i < (int)parent.size(); i++) parent[i] = find(i);
for (int i = 0; i < (int)parent.size(); i++) {
if (parent[i] != i) continue;
for (int g = 0; g < 3; g++) {
if (tab[i][g] != -1) tab[i][g] = find(tab[i][g]);
}
}
}
bool scanOnce() {
bool changed = false;
compress();
int rows = (int)parent.size();
for (int c = 0; c < rows; c++) {
if (find(c) != c) continue;
for (const auto &r : rels) {
int len = (int)r.size();
int l = 0, left = c;
while (l < len) {
left = find(left);
int nxt = tab[left][r[l]];
if (nxt == -1) break;
left = find(nxt);
l++;
}
int rr = len, right = c;
while (rr > l) {
right = find(right);
int nxt = tab[right][inv[r[rr - 1]]];
if (nxt == -1) break;
right = find(nxt);
rr--;
}
if (rr == l) {
if (find(left) != find(right)) changed |= unite(left, right);
} else if (rr == l + 1) {
changed |= defineEdge(left, r[l], right);
}
}
}
return changed;
}
vector<array<int, 3>> run() {
while (true) {
while (scanOnce()) {}
compress();
int row = -1, gen = -1;
for (int i = 0; i < (int)parent.size() && row == -1; i++) {
if (find(i) != i) continue;
for (int g = 0; g < 3; g++) {
if (tab[i][g] == -1) {
row = i;
gen = g;
break;
}
}
}
if (row == -1) break;
defineEdge(row, gen, newCoset());
}
compress();
vector<int> reps, id(parent.size(), -1);
for (int i = 0; i < (int)parent.size(); i++) {
if (find(i) == i) {
id[i] = (int)reps.size();
reps.push_back(i);
}
}
vector<array<int, 3>> res(reps.size());
for (int i = 0; i < (int)reps.size(); i++) {
int r = reps[i];
for (int g = 0; g < 3; g++) res[i][g] = id[find(tab[r][g])];
}
return res;
}
};
vector<vector<int>> makeRelators(const string &s) {
vector<vector<int>> base;
base.push_back({0, 0});
base.push_back({1, 1, 1});
vector<int> w;
for (char c : s) w.push_back(c == 'A' ? 0 : 1);
base.push_back(w);
vector<int> iw;
for (int i = (int)w.size() - 1; i >= 0; i--) iw.push_back(w[i] == 0 ? 0 : 2);
base.push_back(iw);
set<vector<int>> seen;
vector<vector<int>> rels;
for (const auto &r : base) {
int len = (int)r.size();
for (int shift = 0; shift < len; shift++) {
vector<int> cur;
for (int i = 0; i < len; i++) cur.push_back(r[(shift + i) % len]);
if (seen.insert(cur).second) rels.push_back(cur);
}
}
return rels;
}
using Mat = vector<vector<ll>>;
Mat mulMat(const Mat &a, const Mat &b) {
int n = (int)a.size();
Mat c(n, vector<ll>(n, 0));
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) if (a[i][k]) {
for (int j = 0; j < n; j++) if (b[k][j]) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}
vector<ll> mulVec(const vector<ll> &v, const Mat &m) {
int n = (int)v.size();
vector<ll> res(n, 0);
for (int i = 0; i < n; i++) if (v[i]) {
for (int j = 0; j < n; j++) if (m[i][j]) {
res[j] = (res[j] + v[i] * m[i][j]) % MOD;
}
}
return res;
}
int main() {
setIO();
int q;
cin >> q;
while (q--) {
string s, t;
ll n;
cin >> s >> t >> n;
ToddCoxeter tc(makeRelators(s));
auto trans = tc.run();
int m = (int)trans.size();
int target = 0;
for (char c : t) target = trans[target][c == 'A' ? 0 : 1];
Mat mat(m, vector<ll>(m, 0));
for (int i = 0; i < m; i++) {
mat[i][trans[i][0]]++;
mat[i][trans[i][1]]++;
}
vector<ll> vec(m, 0);
vec[0] = 1;
while (n > 0) {
if (n & 1) vec = mulVec(vec, mat);
mat = mulMat(mat, mat);
n >>= 1;
}
cout << vec[target] % MOD << char(10);
}
}