题目大意.

这题的加强版：给定替换规则（即对于所有 $8$$8$ 组 XXX 给定替换结果）。

我们知道对于 232 号规则 00010111（即原题），我们只需要把串在某个自动机上跑；对于此题我们也大胆猜测这样的自动机存在。

那么问题来了，如何求出这个自动机呢？

我们考虑分辨出自动机的每个节点：每个节点都是一个串的等价类，同一个等价类的 $u,v$$u,v$ 满足对于任意 $s$$s$，$us$$us$ 与 $vs$$vs$ 胜负相同。

由毛估估可得，自动机的节点数很少，所以我们只需要对很短的 $s$$s$ 确认上述事实（这个结论似乎称作泵引理，具体参见《浅谈有限状态自动机及其应用》（Cyanic，2021 集训队论文集）），就可以完美划分出所有等价类。等价类之间的转移关系也就显然了。

打表机如下。

​x
#include<bits/stdc++.h>
using namespace std;

int w[8] = {1, 1, 0, 0, 0, 1, 0, 0};

struct node {
    int s[30], w;
    int len;
    void calc() {
        w = 0;
        for (int i = 0; i < len; i++)
            w = (w << 1) | s[i];
    }
} A[2048]; int idx;
bool operator < (const node a, const node b) {
    if (a.len != b.len) return a.len < b.len;
    return a.w < b.w;
}
node operator + (const node a, const int x) {
    node ta; ta.len = a.len + 2;
    for (int i = 0; i < 30; i++) ta.s[i] = a.s[i];
    ta.s[ta.len - 2] = x & 1;
    ta.s[ta.len - 1] = x >> 1;
    ta.w = (a.w << 2) + ((x & 1) << 1) + (x >> 1);
    return ta;
}

int fa[2048];
node rt[30];
int ff(int x) { return fa[x] == x ? x : fa[x] = ff(fa[x]); }

map<node, int> qaq, qwq;
int getqaq(node u) {
    if (u.len == 1) return u.s[0];
    if (qaq.count(u)) return qaq[u];

    int ans = 0;
    for (int i = 2; i < u.len; i++) {
        int v = w[(u.s[i] << 2) | (u.s[i - 1] << 1) | u.s[i - 2]];
        node tu; tu.len = u.len - 2;
        for (int j = 0; j < i - 2; j++)
            tu.s[j] = u.s[j];
        tu.s[i - 2] = v;
        for (int j = i + 1; j < u.len; j++)
            tu.s[j - 2] = u.s[j];
        tu.calc();
        ans |= getqaq(tu);
    }
    qaq[u] = ans;
    return ans;
}

int isequal(const node u, const node v) {
    if (getqaq(u) != getqaq(v)) return 0;
    for (int d = 0; d < 4; d++)
        if (getqaq(u + d) != getqaq(v + d)) return 0;
    for (int d1 = 0; d1 < 4; d1++)
    for (int d2 = 0; d2 < 4; d2++)
        if (getqaq((u + d1) + d2) != getqaq((v + d1) + d2)) return 0;
    for (int d1 = 0; d1 < 4; d1++)
    for (int d2 = 0; d2 < 4; d2++)
    for (int d3 = 0; d3 < 4; d3++)
        if (getqaq(((u + d1) + d2) + d3) != getqaq(((v + d1) + d2) + d3)) return 0;
    return 1;
}

int clr[2048], tot;

bool vis[2048][2048];

void solve() {
    memset(vis, 0, sizeof(vis));
    qaq.clear();
    A[0].len = 1, fa[0] = 0, A[0].s[0] = 0, A[0].w = 0;
    A[1].len = 1, fa[1] = 1, A[1].s[0] = 1, A[1].w = 1;
    idx = 1;
    int l = 0, r = 1;
    for (int i = 1; i <= 4; i++) {
        for (int x = l; x <= r; x++)
        for (int d = 0; d < 4; d++) {
            A[++idx] = A[x] + d;
            fa[idx] = idx;
        }
        l = r + 1, r = idx;
    }

    for (int i = 0; i <= idx; i++)
    for (int j = i + 1; j <= idx; j++) if (!vis[ff(i)][ff(j)] && ff(i) != ff(j))
        if (isequal(A[i], A[j])) {
            int fi = ff(i), fj = ff(j);
            if (A[fi].len < A[fj].len) fa[fj] = fi;
            else fa[fi] = fj;
        }
        else vis[ff(i)][ff(j)] = 1, vis[ff(j)][ff(i)] = 1;
        
    tot = 0;
    for (int i = 0; i <= idx; i++) if (ff(i) == i) {
        clr[i] = ++tot;
        rt[tot] = A[i];
        // printf("%d : ", A[i].len);
        // for (int j = 0; j < A[i].len; j++) printf("%d", A[i].s[j]);
        // printf("\n");
    }
    qwq.clear();
    for (int i = 0; i <= idx; i++) qwq[A[i]] = clr[ff(i)];

    printf("{%d, ", tot); // 入口
    printf("{0, ");
    for (int i = 0; i <= idx; i++) if (ff(i) == i) printf((clr[i] == tot ? "%d}, " : "%d, "), getqaq(A[i]));
    printf("{0, ");
    for (int i = 0; i <= idx; i++) if (ff(i) == i)
        printf((clr[i] == tot ? "%d}, " : "%d, "), qwq[A[i] + 0]);
    printf("{0, ");
    for (int i = 0; i <= idx; i++) if (ff(i) == i)
        printf((clr[i] == tot ? "%d}, " : "%d, "), qwq[A[i] + 1]);
    printf("{0, ");
    for (int i = 0; i <= idx; i++) if (ff(i) == i)
        printf((clr[i] == tot ? "%d}, " : "%d, "), qwq[A[i] + 2]);
    printf("{0, ");
    for (int i = 0; i <= idx; i++) if (ff(i) == i)
        printf((clr[i] == tot ? "%d}};\n" : "%d, "), qwq[A[i] + 3]);
}

int main() {
    freopen("1.out", "w", stdout);
    for (int W = 0; W < 1 << 8; W++) {
    // int W = 104;
        for (int i = 0; i < 8; i++) w[i] = (W >> i) & 1;
        printf("dfa[%d] = ", W);
        solve();
        cerr << "/se " << W << "\n";
    }
}