#include <cstdio> #include <set> #include <vector> using namespace std; long long MOD = 1'000'000'007LL; long long pow(long long a, long long b) { if (b == 1) { return a % MOD; } long long c = pow(a, b/2); c = (c * c) % MOD; if (b & 1) { c = (c * a) % MOD; } return c; } class Permutation { public: vector<int> s; Permutation(const vector<int>& s) : s(s) {} Permutation operator*(const Permutation& other) { vector<int> res(s.size()); for (int i = 0; i<s.size(); i++) { res[i] = s[other.s[i]]; } return Permutation(res); } bool operator<(const Permutation& other) const { for (int i = 0; i< s.size(); i++) { if (s[i] != other.s[i]) { return s[i] < other.s[i]; } } return false; } int count_inversions() const { int sum = 0; for (int i = 0; i<s.size(); i++) { for (int j = i + 1; j<s.size(); j++) { if (s[i] > s[j]) sum++; } } return sum; } }; void gen(int i, int iii, int j, int jjj, vector<Permutation>& all, set<Permutation>& all_set) { for (int ii = i; ii < iii; ii++) { for (int jj = j; jj < jjj; jj++) { auto p = all[ii] * all[jj]; if (!all_set.count(p)) { all.push_back(p); all_set.insert(p); } } } } int main () { int n, k; scanf("%d%d", &n, &k); vector<Permutation> all; set<Permutation> all_set; for (int i = 0; i<k; i++) { vector<int> perm; for (int j = 0, a; j<n; j++) { scanf("%d", &a); perm.push_back(a - 1); } auto p = Permutation(perm); all.push_back(p); all_set.insert(p); } int i = 0, j = 0, l = k; while (j != l) { if (n * ((l-j) * (l-j) + 2 * (l-j) * (j - i)) > 3'000'000) { printf("%lld\n", (n * (n-1) * pow(4, MOD - 2)) % MOD); return 0; } gen(i, j, j, l, all, all_set); gen(j, l, i, j, all, all_set); gen(j, l, j, l, all, all_set); i = j; j = l; l = all.size(); } long long result = 0; for (const Permutation& perm : all) { result += perm.count_inversions(); } result = (result * pow(all.size(), MOD - 2)) % MOD; printf("%lld\n", result); 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 94 95 96 97 98 99 100 101 102 103 | #include <cstdio> #include <set> #include <vector> using namespace std; long long MOD = 1'000'000'007LL; long long pow(long long a, long long b) { if (b == 1) { return a % MOD; } long long c = pow(a, b/2); c = (c * c) % MOD; if (b & 1) { c = (c * a) % MOD; } return c; } class Permutation { public: vector<int> s; Permutation(const vector<int>& s) : s(s) {} Permutation operator*(const Permutation& other) { vector<int> res(s.size()); for (int i = 0; i<s.size(); i++) { res[i] = s[other.s[i]]; } return Permutation(res); } bool operator<(const Permutation& other) const { for (int i = 0; i< s.size(); i++) { if (s[i] != other.s[i]) { return s[i] < other.s[i]; } } return false; } int count_inversions() const { int sum = 0; for (int i = 0; i<s.size(); i++) { for (int j = i + 1; j<s.size(); j++) { if (s[i] > s[j]) sum++; } } return sum; } }; void gen(int i, int iii, int j, int jjj, vector<Permutation>& all, set<Permutation>& all_set) { for (int ii = i; ii < iii; ii++) { for (int jj = j; jj < jjj; jj++) { auto p = all[ii] * all[jj]; if (!all_set.count(p)) { all.push_back(p); all_set.insert(p); } } } } int main () { int n, k; scanf("%d%d", &n, &k); vector<Permutation> all; set<Permutation> all_set; for (int i = 0; i<k; i++) { vector<int> perm; for (int j = 0, a; j<n; j++) { scanf("%d", &a); perm.push_back(a - 1); } auto p = Permutation(perm); all.push_back(p); all_set.insert(p); } int i = 0, j = 0, l = k; while (j != l) { if (n * ((l-j) * (l-j) + 2 * (l-j) * (j - i)) > 3'000'000) { printf("%lld\n", (n * (n-1) * pow(4, MOD - 2)) % MOD); return 0; } gen(i, j, j, l, all, all_set); gen(j, l, i, j, all, all_set); gen(j, l, j, l, all, all_set); i = j; j = l; l = all.size(); } long long result = 0; for (const Permutation& perm : all) { result += perm.count_inversions(); } result = (result * pow(all.size(), MOD - 2)) % MOD; printf("%lld\n", result); return 0; } |