Grok 没有一次对的，GPT2次过
原题链接：787.Compound Escape--Platinum
2025-11-18 10:55:20
发布于：上海
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;
ll modpow(ll a, ll e=MOD-2){
ll r=1;
a %= MOD;
while(e){
if(e & 1) r = (r * a) % MOD;
a = (a * a) % MOD;
e >>= 1;
}
return r;
}
struct DSU {
int n;
vector<int> p, r;
DSU(int n=0): n(n), p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]x?x:p[x]=find(p[x]); }
bool unite(int a,int b){
a=find(a); b=find(b);
if(ab) return false;
if(r[a]<r[b]) swap(a,b);
p[b]=a;
if(r[a]==r[b]) r[a]++;
return true;
}
};
struct Edge { int u,v; int w; };
ll det_mod_inplace(vector<vector<ll>>& A){ // A is n x n, compute det mod MOD
int n = (int)A.size();
ll det = 1;
for (int i = 0; i < n; ++i) {
int pivot = -1;
for (int r = i; r < n; ++r) if ((A[r][i] % MOD + MOD) % MOD != 0) { pivot = r; break; }
if (pivot == -1) return 0;
if (pivot != i) {
swap(A[pivot], A[i]);
det = (MOD - det) % MOD;
}
ll val = (A[i][i] % MOD + MOD) % MOD;
det = det * val % MOD;
ll inv = modpow(val);
// eliminate below
for (int r = i+1; r < n; ++r) {
if (A[r][i] == 0) continue;
ll factor = (A[r][i] % MOD + MOD) % MOD * inv % MOD;
// A[r][c] -= factor * A[i][c]
for (int c = i; c < n; ++c) {
ll t = (A[r][c] - factor * (A[i][c] % MOD + MOD) % MOD) % MOD;
A[r][c] = t;
}
}
}
return (det%MOD + MOD) % MOD;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,K;
if(!(cin>>N>>K)) return 0;
// node id = iK + j
vector<Edge> edges;
edges.reserve(N(K-1) + (N-1)*K);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < K-1; ++j) {
int c; cin >> c;
edges.push_back({i*K + j, i*K + j+1, c});
}
}
for (int j = 0; j < K; ++j) {
for (int i = 0; i < N-1; ++i) {
int c; cin >> c;
edges.push_back({i*K + j, (i+1)*K + j, c});
}
}
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.w < b.w; });
int total_nodes = N * K;
DSU dsu(total_nodes);
ll answer = 1;
int m = (int)edges.size();
int idx = 0;
// temporary containers reused each weight-group
unordered_map<int,int> root_to_idx; // map DSU-root -> local idx
vector<pair<int,int>> group_pairs; // pairs of roots (a,b)
vector<int> nodes_list; // list of roots used
while (idx < m) {
int j = idx;
int w = edges[idx].w;
while (j < m && edges[j].w == w) ++j;
root_to_idx.clear();
group_pairs.clear();
nodes_list.clear();
root_to_idx.reserve((j - idx) * 2 + 10);
// collect useful edges (those connecting different DSU components)
for (int t = idx; t < j; ++t) {
int ru = dsu.find(edges[t].u);
int rv = dsu.find(edges[t].v);
if (ru == rv) continue;
auto it = root_to_idx.find(ru);
if (it == root_to_idx.end()) {
int id = (int)root_to_idx.size();
root_to_idx.emplace(ru, id);
nodes_list.push_back(ru);
}
it = root_to_idx.find(rv);
if (it == root_to_idx.end()) {
int id = (int)root_to_idx.size();
root_to_idx.emplace(rv, id);
nodes_list.push_back(rv);
}
group_pairs.emplace_back(root_to_idx[ru], root_to_idx[rv]);
}
if (!group_pairs.empty()) {
int S = (int)root_to_idx.size();
// build adjacency (count multiedges) using vector<unordered_map<int,int>>
vector<unordered_map<int,int>> adj(S);
for (auto &pr : group_pairs) {
int a = pr.first, b = pr.second;
if (a == b) continue;
adj[a][b] += 1;
adj[b][a] += 1;
}
// find connected components in this small graph
vector<int> vis(S, 0);
vector<int> stack;
stack.reserve(S);
for (int s = 0; s < S; ++s) {
if (vis[s]) continue;
// BFS/stack to collect component
vector<int> comp;
stack.clear();
stack.push_back(s);
vis[s] = 1;
while (!stack.empty()) {
int u = stack.back(); stack.pop_back();
comp.push_back(u);
for (auto &kv : adj[u]) {
int v = kv.first;
if (!vis[v]) { vis[v] = 1; stack.push_back(v); }
}
}
if ((int)comp.size() == 1) continue; // single node, no internal edges -> contributes factor 1
int sz = (int)comp.size();
// map comp node -> 0..sz-1
unordered_map<int,int> cmap;
cmap.reserve(sz*2);
for (int i = 0; i < sz; ++i) cmap[comp[i]] = i;
// build Laplacian (sz x sz)
vector<vector<ll>> L(sz, vector<ll>(sz, 0));
for (int i = 0; i < sz; ++i) {
int u = comp[i];
for (auto &kv : adj[u]) {
int v = kv.first;
int cnt = kv.second;
if (cmap.find(v) == cmap.end()) continue;
int iv = cmap[v];
if (iv == i) continue;
L[i][i] += cnt;
L[i][iv] -= cnt;
}
}
// build (sz-1)x(sz-1) matrix by removing last row/col
int nn = sz - 1;
vector<vector<ll>> M(nn, vector<ll>(nn, 0));
for (int r = 0; r < nn; ++r)
for (int c = 0; c < nn; ++c)
M[r][c] = (L[r][c] % MOD + MOD) % MOD;
ll ways = det_mod_inplace(M);
answer = (answer * ways) % MOD;
}
}
// finally unite all edges in this equal-weight group
for (int t = idx; t < j; ++t) {
dsu.unite(edges[t].u, edges[t].v);
}
idx = j;
}
cout << (answer % MOD + MOD) % MOD << "\n";
return 0;
}
这里空空如也
有帮助，赞一个