题目链接：Codeforces 1138E

在国家 $N$ 中，有 $n$ 个城市通过 $m$ 条单向道路连接。尽管这个国家看起来并不是那么引人注目，但是这里有两件很有意思的事情。首先，这里的一周有 $d$ 天；另外，每个城市恰好有一个博物馆。

旅行社的员工知道每个博物馆的开放日期，他们正在为游客们制定一项新的旅游计划。旅游从标号为 $1$ 的首都城市出发，并且旅游的第一天必须在某一周的第一天。每天白天，如果当前城市的博物馆开放，那么游客可以进入博物馆参观；否则什么都做不了。晚上，游客要么结束旅游，要么通过道路前往下一个城市。注意，旅游过程中允许重复经过同一个城市。

你需要为旅游制定一条路线，使得在旅游期间参观的不同博物馆数量最多。

数据范围：$1 \le n \le 10 ^ 5$，$0 \le m \le 10 ^ 5$，$1 \le d \le 50$。

Solution

首先把每个点 $u$ 拆成 $d$ 个点 $u_0, u_1, \dots, u_{d - 1}$，这样一条边 $(u, v)$ 转化为 $(u_0, v_1), (u_1, v_2), \dots, (u_{d - 1}, v_0)$ 这 $d$ 条边。由于同一个强连通分量内的点是相互可达的，那么我们把这张图缩成一个 $\text{DAG}$，然后进行 $\text{DP}$ 计数。

但是我代码写到一半突然发现一个问题：如果有两个点 $u_i, u_j(i \ne j)$ 存在于不同的强连通分量中，且这两个强连通分量可达（拓扑排序或 $\text{DFS}$ 时会重复计数），怎么才能不重复计数？难道需要 $\text{set}$ 去重？启发式合并？并且支持撤回操作？

接下来我们就证明如下结论：如果从点 $u_i$ 可以到达 $u_j(i \ne j)$，那么这两个点一定在同一个强连通分量中。设 $\Delta = j - i$，那么一定存在这样一条路径：$u_i \rightarrow u_j \rightarrow u_{j + \Delta} \rightarrow u_{j + 2\Delta} \rightarrow \dots \rightarrow u_{j + (d - 1)\Delta}$（此处的下标均对 $d$ 取模），发现 $j + (d - 1)\Delta = i \pmod d$，因此一定可以从 $u_j$ 回到 $u_i$。这意味着 $u_i, u_j$ 一定在同一个强连通分量中。

证明了这个结论后，可以直接 $\text{tarjan}$ 缩点后 $\text{DP}$ 了。

时间复杂度：$\mathcal O((n + m) \cdot d)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 5e6 + 5;

int n, m, d, tag[N], sz[N], f[N];
int cnt, idx, top, stk[N], dfn[N], low[N], scc[N];
bool vis[N];
char s[100005][51];

template <int N, int M>
struct Graph {
    int tot, lnk[N], ter[M], nxt[M];
    void add(int u, int v) {
        ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
    }
};

Graph<N, N> G1, G2;

int id(int x, int t) {
    return (x - 1) * d + t + 1;
}
void tarjan(Graph<N, N> &G, int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u, vis[u] = true;
    for (int i = G.lnk[u]; i; i = G.nxt[i]) {
        int v = G.ter[i];
        if (!dfn[v]) {
            tarjan(G, v);
            low[u] = std::min(low[u], low[v]);
        } else {
            if (vis[v]) low[u] = std::min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++cnt;
        do {
            u = stk[top--], scc[u] = cnt, vis[u] = false;
        } while (dfn[u] != low[u]);
    }
}
int dfs(Graph<N, N> &G, int u) {
    if (f[u]) return f[u];
    for (int i = G.lnk[u]; i; i = G.nxt[i]) {
        f[u] = std::max(f[u], dfs(G, G.ter[i]));
    }
    return f[u] += sz[u];
}
int main() {
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        for (int j = 0; j < d; j++) {
            G1.add(id(u, j), id(v, (j + 1) % d));
        }
    }
    for (int i = 1; i <= n; i++) scanf("%s", s[i]);
    tarjan(G1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < d; j++) {
            int u = id(i, j);
            if (s[i][j] == '1' && tag[scc[u]] != i) {
                tag[scc[u]] = i, sz[scc[u]]++;
            }
            for (int i = G1.lnk[u]; i; i = G1.nxt[i]) {
                int v = G1.ter[i];
                if (scc[u] != scc[v]) G2.add(scc[u], scc[v]);
            }
        }
    }
    printf("%d\n", dfs(G2, scc[1]));
    return 0;
}