题解 CF516E 【Drazil and His Happy Friends】

· · 题解

CF516E Drazil and His Happy Friends

题意

题解

首先考虑 \gcd(n,m) \ne 1，我们可以按照 \bmod \gcd(n,m) 分组，不同组之间显然互不影响。

那么根据裴蜀定理，有解的充要条件为每组内至少有一个人是快乐的。

若有解，将每一组的答案求出来后取 \max 即可。

考虑某一组，此时不妨设 n > m，同时有 \gcd(n,m) = 1。

首先有一个结论：如果 n 个男生都快乐了，那么除非当前天数小于 m，否则所有女生一定也都是快乐的。这是因为往前的 m 天里，由于所有男生都快乐了，因此要么是原本就都快乐，要么是快乐的影响另一个。

那么我们只需要求出最后一个变快乐的男生即可。为了方便，如果女生 x 初始快乐，那么将男生 x 也标记为初始快乐。

对于一个男生 x，若它在第 t 天变快乐，那么他就会通过女生 t \bmod m 在第 t+m 天使男生 (t+m)\bmod n 变快乐。

考虑同余最短路，则有连边 i \stackrel{m}{\longrightarrow} (i+m)\bmod n。另外，建立一个虚拟源点 S，对于初始快乐的男生 i，有连边 S \stackrel{i}{\longrightarrow} i。

则最后所有点的最短路的最大值就是这一组的答案。

但是这样点数是 10^9 级别的，无法承受。

注意到这样的建图方式实际上会形成一个环，因此考虑删掉一些并不重要的点：如果 i 和 (i+m) \bmod n 初始都是不快乐的，那么 i 一定会在 (i+m) \bmod n 之前变快乐，因此 i 就没用了。

那么我们可以只保留 i 或 (i+m) \bmod n 初始快乐的节点，这样点数只有 10^5 级别了。

如何进行连边呢？

设 i 初始快乐的节点为 A 类点，编号为 A_i；(i+m) \bmod n 初始快乐的节点为 B 类点，编号为 B_i。

我们要连三类边：

  1. S \stackrel{i}{\longrightarrow} A_i
  2. B_i \stackrel{m}{\longrightarrow} A_i
  3. A_i \stackrel{xm}{\longrightarrow} B_j

第 1,2 类边都很容易，问题在第 3 类边上。要求出 B_j，求出 A_j 即可，那么此时实际上问题转化为在模 n 意义下以 m 为跨度的有向环上，从每一个 A_i 往后遇到的第一个 A_j 是哪个。

我们可以考虑 i 最小的 A_i，求出从 A_i 开始分别要经过多少个 m 到达其他 A 类点 A_j，即求 i + xm \equiv j \pmod n 的最小非负整数解 x，使用 exgcd 即可。注意实现时其实只用求一次 exgcd。

求完后，对所有 x 排序，即可求出环上 A 类点依次被经过的顺序，也就求出了每一个 A_i 往后遇到的第一个 A_j 是哪个。

这样第 3 类边也能够连上了。

注意最后还要特判天数小于 m 的情况。

总时间复杂度 \mathcal O(n \log n)。

代码

#define Fail return print(-1), 0

const int N = 1e5 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, d, B, G, b[N], g[N];
vi a[N<<1], f[N<<1];
ll ans;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int exgcd(int a, int b, int &x, int &y, int d = 0) { return b ? (d = exgcd(b, a % b, y, x), y -= a / b * x, d) : (x = 1, y = 0, a); }

inline ll solve(vi a, vi b) {
    vi s = a;
    for (ui i = 0; i < b.size(); i++) s.pb(b[i]);
    sort(s.begin(), s.end());
    int k = unique(s.begin(), s.end()) - s.begin(), x, y;
    if (n == k) {
        int c[m];
        memset(c, 0, sizeof(c));
        for (ui i = 0; i < a.size(); i++) if (a[i] < m) ++c[a[i]];
        for (ui i = 0; i < b.size(); i++) if (b[i] < m) ++c[b[i]];
        for (int i = m - 1; ~i; i--) if (c[i] == 1) return i;
        return -1;
    }
    vector< pair< int, ll > > e[2*k+1];
    for (int i = 0; i < k; i++) e[2*k].pb(mp(i, s[i])), e[i+k].pb(mp(i, m));
    exgcd(m, n, x, y), x = (x % n + n) % n;
    pi p[k];
    for (int i = 0; i < k; i++) p[i] = mp(1ll * x * (s[i] - s[0]) % n, i);
    sort(p, p + k);
    for (int i = 0, j = 1 % k; i < k; i++, j = (++j == k) ? 0 : j) e[p[i].se].pb(mp(p[j].se + k, 1ll * m * (p[j].fi - p[i].fi - 1 < 0 ? p[j].fi - p[i].fi - 1 + n : p[j].fi - p[i].fi - 1)));
    map< int, int > h;
    for (int i = 0; i < k; i++) h[s[i]] = i;
    for (int i = 0; i < k; i++)
        if (h.find((s[i] + m) % n) != h.end()) {
            int j = h[(s[i]+m)%n];
            e[i].pb(mp(j + k, 0)), e[j+k].pb(mp(i, 0));
        }
    pq< pair< ll, int > > q;
    int v[2*k+1];
    ll d[2*k+1], now = 0;
    memset(v, 0, sizeof(v));
    memset(d, 0x3f, sizeof(d));
    q.push(mp(0, 2 * k)), d[2*k] = 0;
    while (q.size()) {
        int x = q.top().se;
        q.pop();
        if (v[x]) continue;
        v[x] = 1, now = max(now, d[x]);
        for (ui i = 0; i < e[x].size(); i++) {
            int y = e[x][i].fi;
            ll z = e[x][i].se;
            if (d[y] > d[x] + z) d[y] = d[x] + z, q.push(mp(-d[y], y));
        }
    }
    return now;
}

int main() {
    rd(n), rd(m), rd(B);
    for (int i = 1; i <= B; i++) rd(b[i]);
    rd(G);
    for (int i = 1; i <= G; i++) rd(g[i]);
    if (n < m) swap(n, m), swap(B, G), swap(b, g);
    if ((d = gcd(n, m)) > B + G) Fail;
    n /= d, m /= d;
    for (int i = 1; i <= B; i++) a[b[i]%d].pb(b[i] / d);
    for (int i = 1; i <= G; i++) f[g[i]%d].pb(g[i] / d);
    for (int i = 0; i < d; i++)
        if (!a[i].size() && !f[i].size()) Fail;
    for (int i = 0; i < d; i++) ans = max(ans, solve(a[i], f[i]) * d + i);
    print(ans);
    return 0;
}