B. Black and white

题意：给定一个n*m的棋盘，起初全白，将一个格子染黑需要代价$a[i][j]$，若某个矩形的四个角里有三个已经是黑色，则将第四个角染黑不需要任何代价，问将整个棋盘染黑的最小代价

转化为一个联通性问题，点1~n代表1~n行，点n+1~n+m代表1~m列，i和j+n之间连一条边权为$a[i][j]$用的边。$(i,j+n)$联通代表$(i,j)$这个格子已被染黑，于是将整个棋盘染黑等价于整张图联通，即求该图的最小生成树

为啥问题等价呢，考虑$(i,j)$联通的两种可能性：

$(i,j+n)$连了一条边，说明直接染黑
$(i_1,j_2)$通过一些中间边如$(i_1,j_1),(i_2,j_1),(i_2,j_2)$联通，意味着$(i_1,j_1),(i_2,j_1),(i_2,j_2)$已被染黑，显然这四个点构成矩形的四个角，$(i_1,j_2)$可以不花费代价染黑

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e4 + 5;

struct Edge {
    int f, t;
};

vector<Edge> E[100005];

ll ans;

int n, m, a, b, c, d, p, fa[N];

int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }

int nxt(int x) {
    return (1ll * x * x * b + 1ll * x * c + d) % p;
}

int main() {
    scanf("%d %d %d %d %d %d %d", &n, &m, &a, &b, &c, &d, &p);
    int now = a;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            now = nxt(now);
            E[now].push_back({i, j + n});
        }
    }
    for (int i = 1; i <= n + m; i++) fa[i] = i;
    int cnt = 0;
    for (int i = 0; i <= 100000; i++) {
        for (auto x : E[i]) {
            int u = getfa(x.f), v = getfa(x.t);
            if (u == v) continue;
            fa[u] = v;
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}