#include <bits/stdc++.h>
using namespace std;
constexpr int P = 1000000007;
int inv(int a)
{
int x = 1, y = 0, q = P;
int pos = 0;
while (a > 0) {
int r = q % a;
q = q/a;
int h = q*x + y;
y = x;
x = h;
q = a;
a = r;
pos = !pos;
}
return pos ? y : (P - y);
}
int n;
using Perm = array<int, 3 * 1024>;
vector<Perm> perms;
vector<Perm> visited;
using Pair = pair<int, int>;
void Read()
{
int k;
scanf("%d%d", &n, &k);
perms.resize(k);
for (int i = 0; i < k; i++)
for (int j = 0; j < n; j++)
{
int a;
scanf("%d", &a);
perms[i][j] = a - 1;
}
}
vector<Pair> component;
void DFS(int a, int b)
{
component.emplace_back(a, b);
visited[a][b] = 1;
for (Perm& p : perms)
{
int i = p[a], j = p[b];
if (!visited[i][j])
DFS(i, j);
}
}
int Visit(int a, int b)
{
DFS(a, b);
int count = 0;
for (auto [i, j] : component)
count += i < j;
int res = int64_t(count) * (component.size() - count) % P;
if (count)
res = (int64_t(res) * inv(component.size())) % P;
component.clear();
return res;
}
void Solve()
{
int res = 0;
visited.resize(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
visited[i][j] = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (!visited[i][j])
res = (res + Visit(i, j)) % P;
printf("%d\n", res);
}
int main()
{
Read();
Solve();
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 92 93 | #include <bits/stdc++.h> using namespace std; constexpr int P = 1000000007; int inv(int a) { int x = 1, y = 0, q = P; int pos = 0; while (a > 0) { int r = q % a; q = q/a; int h = q*x + y; y = x; x = h; q = a; a = r; pos = !pos; } return pos ? y : (P - y); } int n; using Perm = array<int, 3 * 1024>; vector<Perm> perms; vector<Perm> visited; using Pair = pair<int, int>; void Read() { int k; scanf("%d%d", &n, &k); perms.resize(k); for (int i = 0; i < k; i++) for (int j = 0; j < n; j++) { int a; scanf("%d", &a); perms[i][j] = a - 1; } } vector<Pair> component; void DFS(int a, int b) { component.emplace_back(a, b); visited[a][b] = 1; for (Perm& p : perms) { int i = p[a], j = p[b]; if (!visited[i][j]) DFS(i, j); } } int Visit(int a, int b) { DFS(a, b); int count = 0; for (auto [i, j] : component) count += i < j; int res = int64_t(count) * (component.size() - count) % P; if (count) res = (int64_t(res) * inv(component.size())) % P; component.clear(); return res; } void Solve() { int res = 0; visited.resize(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) visited[i][j] = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (!visited[i][j]) res = (res + Visit(i, j)) % P; printf("%d\n", res); } int main() { Read(); Solve(); return 0; } |
English