P6896题解

· · 题解

Link

P6896 [ICPC2014 WF]Maze Reduction

Solution

首先你可能要花一定的时间理解一下题意。

然后你发现就是要你判断房间的等价类的个数。

要做这个问题，我们不妨先考虑我们判断房间是否等价的手段。直接从点的角度出发，我们不妨设我们从某个边 u 进入点 x，从边 v 进入点 y ，那么两个点等价，当且仅当点 x 从 u 起与点 y 从 v 起的边序列相等，而两个边相等，又要求两个边的终点等价。

那么我们再考虑需要判断的点。这时，我们有选择第一条走的边的权力，也就是说，只要两个点的边序列循环移位后相等，两个点就相等。

这是一个复杂结构的判等问题，我们考虑hash。

这个hash值显然是递推出来的。我们考虑一下要记哪些东西：

然后你发现记这么一点不能递推，于是你想了想，再记一维：

然后万事大吉。最后我们递推hash值时，只要从进入边顺时针遍历，就可以保证边序列的信息记录到了hash值中。

唔……具体hash的递推过程比较难表达，大家可以看看代码。

然后就是那个循环移位的解决：其实也很简单，只需要把 f_{n,x,-} 看成一个字符串，求出一个最小表示，然后判相等的时候直接一个字符串比较就OK了。

注意如果你是用Lyndon分解求最小表示的要注意 |s| = 1 的情况。

Code

#include <cstdio>

#define _N 110
#define _P 998244353

struct Mod {
    int val;
    Mod() {
        val = 0;
    }
    Mod(long long x) {
        val = x >= 0 ? x % _P : x % _P + _P;
    }
};

bool inline operator ==(const Mod& left, const Mod& right) {
    return left.val == right.val;
}
bool inline operator !=(const Mod& left, const Mod& right) {
    return left.val != right.val;
}
bool inline operator <=(const Mod& left, const Mod& right) {
    return left.val <= right.val;
}

Mod inline operator +(const Mod& left, const Mod& right) {
    return left.val + right.val;
}
Mod inline operator *(const Mod& left, const Mod& right) {
    return 1ll * left.val * right.val;
}

int n;

int cnt[_N];
int to[_N][_N], id[_N][_N];

Mod f[_N][_N][_N];

Mod tmp[_N << 1];
Mod mnsw[_N][_N];

bool vis[_N];

int qcnt;
int q[_N];

Mod inline hash(Mod left, Mod right) {
    return left * 19260817 + right;
}

void calc_mnsw(Mod* s, Mod* res, int slen) {
    for (int i = 1; i <= slen; i++) {
        tmp[i] = tmp[i + slen] = s[i];
    }
    int resp = 1;
    for (int i = 1, j, k; i <= slen;) {
        for (j = i, k = i + 1; k <= (slen << 1) && tmp[j] <= tmp[k]; k++) {
            j = (tmp[j] == tmp[k] ? j + 1 : i);
        }
        while (i <= j) {
            i += k - j;
            resp = (i <= slen ? i : resp);
        }
    }
    for (int i = 1; i <= slen; i++) {
        res[i] = tmp[resp + i - 1];
    }
}

bool equals(int left, int right) {
    if (cnt[left] != cnt[right]) {
        return false;
    }
    for (int i = 1; i <= n; i++) {
        if (mnsw[left][i] != mnsw[right][i]) {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cnt[i]);
        for (int j = 1; j <= cnt[i]; j++) {
            scanf("%d", &to[i][j]);
            id[i][to[i][j]] = j;
        }
    }
    for (int x = 1; x <= n; x++) {
        for (int i = 1; i <= cnt[x]; i++) {
            f[0][x][i] = cnt[x];
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int x = 1; x <= n; x++) {
            for (int i = 1; i <= cnt[x]; i++) {
                int y = to[x][i];
                for (int j = id[y][x]; j <= cnt[y]; j++) {
                    f[k][x][i] = hash(f[k][x][i], f[k - 1][y][j]);
                }
                for (int j = 1; j < id[y][x]; j++) {
                    f[k][x][i] = hash(f[k][x][i], f[k - 1][y][j]);
                }
            }
        }
    }
    for (int x = 1; x <= n; x++) {
        calc_mnsw(f[n][x], mnsw[x], cnt[x]);
    }
    bool flag = false;
    for (int x = 1; x <= n; x++) {
        if (!vis[x]) {
            vis[x] = true;
            qcnt = 0;
            q[++qcnt] = x;
            for (int y = x + 1; y <= n; y++) {
                if (!vis[y] && equals(x, y)) {
                    vis[y] = true;
                    q[++qcnt] = y;
                }
            }
            if (qcnt > 1) {
                for (int i = 1; i <= qcnt; i++) {
                    printf("%d ", q[i]);
                }
                puts("");
                flag = true;
            }
        }
    }
    if (!flag) {
        puts("none");
    }
    return 0;
}

Inspiration

我认为这道题的思路总体比较自然。首先要读懂复杂的题意，然后注意到这是一个复杂结构的相等判断，于是想到使用hash。

核心结论：