#include<bits/stdc++.h> using namespace std; const int mod = 1000000007; const int stala = 3005; int lider[10000005]; int sz_good[10000005]; int sz_bad[10000005]; vector<vector<int>> v; int f(int a) { if(lider[a] != a) lider[a] = f(lider[a]); return lider[a]; } void u(int a, int b) { int c = f(a), d = f(b); if(c != d) { lider[c] = d; sz_good[d] += sz_good[c]; sz_bad[d] += sz_bad[c]; } } long long rev(long long a) { long long res = 1, act = a, left = mod - 2; while(left != 0) { if(left & 1) res = (res * act) % mod; left /= 2; act = (act * act) % mod; } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a, k; cin>>a>>k; for(int x = 0;x < k; x++) { vector<int> pom; for(int y = 0; y < a; y++) { int c; cin>>c; pom.push_back(c); } v.push_back(pom); } for(int x = 1; x <= a; x++) for(int y = 1; y <= a; y++) { lider[stala * x + y] = stala * x + y; if(x <= y) sz_good[stala * x + y] = 1; else sz_bad[stala * x + y] = 1; } for(int x = 1; x <= a; x++) for(int y = 1; y <= a; y++) for(auto z : v) if(x != y) { int pom1 = z[x - 1], pom2 = z[y - 1]; u(stala * x + y, stala * pom1 + pom2); } pair<long long,long long> p = {0, 0}; for(int x = 1; x <= a; x++) for(int y = x + 1; y <= a; y++) { int lid = f(stala * x + y); long long l = sz_bad[lid], m = sz_good[lid] + sz_bad[lid]; // cout<<x<<" "<<y<<" : "<<l<<" "<<m<<'\n'; if(p == make_pair(0LL, 0LL)) p = make_pair(l, m); else { long long new_l = p.first * m + l * p.second, new_m = p.second * m; new_l %= mod; new_m %= mod; p = {new_l, new_m}; } //cout<<p.first<<" "<<p.second<<'\n'; } cout<<(p.first * rev(p.second)) % mod; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include<bits/stdc++.h> using namespace std; const int mod = 1000000007; const int stala = 3005; int lider[10000005]; int sz_good[10000005]; int sz_bad[10000005]; vector<vector<int>> v; int f(int a) { if(lider[a] != a) lider[a] = f(lider[a]); return lider[a]; } void u(int a, int b) { int c = f(a), d = f(b); if(c != d) { lider[c] = d; sz_good[d] += sz_good[c]; sz_bad[d] += sz_bad[c]; } } long long rev(long long a) { long long res = 1, act = a, left = mod - 2; while(left != 0) { if(left & 1) res = (res * act) % mod; left /= 2; act = (act * act) % mod; } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a, k; cin>>a>>k; for(int x = 0;x < k; x++) { vector<int> pom; for(int y = 0; y < a; y++) { int c; cin>>c; pom.push_back(c); } v.push_back(pom); } for(int x = 1; x <= a; x++) for(int y = 1; y <= a; y++) { lider[stala * x + y] = stala * x + y; if(x <= y) sz_good[stala * x + y] = 1; else sz_bad[stala * x + y] = 1; } for(int x = 1; x <= a; x++) for(int y = 1; y <= a; y++) for(auto z : v) if(x != y) { int pom1 = z[x - 1], pom2 = z[y - 1]; u(stala * x + y, stala * pom1 + pom2); } pair<long long,long long> p = {0, 0}; for(int x = 1; x <= a; x++) for(int y = x + 1; y <= a; y++) { int lid = f(stala * x + y); long long l = sz_bad[lid], m = sz_good[lid] + sz_bad[lid]; // cout<<x<<" "<<y<<" : "<<l<<" "<<m<<'\n'; if(p == make_pair(0LL, 0LL)) p = make_pair(l, m); else { long long new_l = p.first * m + l * p.second, new_m = p.second * m; new_l %= mod; new_m %= mod; p = {new_l, new_m}; } //cout<<p.first<<" "<<p.second<<'\n'; } cout<<(p.first * rev(p.second)) % mod; return 0; } |