#include <iostream> #include <vector> #include <numeric> #include <queue> #include <algorithm> using namespace std; struct PosPair { int16_t i, j; }; long long wnk_int=0, wnk_num=0, wnk_den=1; const long long MOD = 1000000007; void add_to_wnk(long long num, long long den) { __int128_t new_wnk_num = (__int128_t)wnk_num*den + (__int128_t)wnk_den*num; __int128_t new_wnk_den = (__int128_t)wnk_den*den; wnk_int += new_wnk_num / new_wnk_den; new_wnk_num %= new_wnk_den; wnk_num = (long long)(new_wnk_num % MOD); wnk_den = (long long)(new_wnk_den % MOD); long long d = gcd(wnk_num, wnk_den); wnk_num = (wnk_num / d); wnk_den = (wnk_den / d); } long long power(long long b, long long e) { if (e==0) return 1; long long half = power(b, e/2); half = (half * half) % MOD; if (e%2) return (half * b) % MOD; else return half; } long long inv(long long x) { return power(x, MOD-2); } int main() { wnk_num=0, wnk_den=1; ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<vector<int16_t>> Gens2(n, vector<int16_t>(k)); for (int i=0; i<k; i++) for (int j=0; j<n; j++) { int x; cin >> x; Gens2[x-1][i] = j; // reverse permutation } vector<vector<bool>> Visited(n, vector<bool>(n)); vector<vector<bool>> Side(n, vector<bool>(n)); queue<PosPair>Q; for (int16_t bi=0; bi<n; bi++) for (int16_t bj=bi+1; bj<n; bj++) if (!Visited[bi][bj]) { Visited[bi][bj] = true; Q.push({bi,bj}); long long cnt_no=1, cnt_o=0; bool collapse = false; while(!Q.empty()) { PosPair pp = Q.front(); Q.pop(); for (int g=0; g<k; g++) { int16_t ii = Gens2[pp.i][g]; int16_t jj = Gens2[pp.j][g]; bool rev = ii > jj; if (rev) swap(ii, jj); if (!Visited[ii][jj]) { Visited[ii][jj] = true; Side[ii][jj] = (Side[pp.i][pp.j] != rev); if (Side[ii][jj]) cnt_o++; else cnt_no++; Q.push({ii,jj}); } else if ((Side[pp.i][pp.j]!=rev) != Side[ii][jj]) collapse = true; } } /* cerr << "collapse=" << collapse << endl; */ /* cerr << "cnt_no=" << cnt_no << endl; */ /* cerr << "cnt_o=" << cnt_o << endl; */ if (collapse) add_to_wnk(cnt_o+cnt_no, 2); else add_to_wnk(2*cnt_o*cnt_no, cnt_o+cnt_no); } /* cout << "Result = " << wnk_num << " / " << wnk_den << endl; */ /* cerr << "wnk_int=" << wnk_int << endl; */ /* cerr << "wnk_num=" << wnk_num << endl; */ /* cerr << "wnk_den=" << wnk_den << endl; */ /* cerr << inv(wnk_den) << endl; */ cout << ((wnk_num * inv(wnk_den) + wnk_int) % MOD) << '\n'; 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 104 105 106 107 108 | #include <iostream> #include <vector> #include <numeric> #include <queue> #include <algorithm> using namespace std; struct PosPair { int16_t i, j; }; long long wnk_int=0, wnk_num=0, wnk_den=1; const long long MOD = 1000000007; void add_to_wnk(long long num, long long den) { __int128_t new_wnk_num = (__int128_t)wnk_num*den + (__int128_t)wnk_den*num; __int128_t new_wnk_den = (__int128_t)wnk_den*den; wnk_int += new_wnk_num / new_wnk_den; new_wnk_num %= new_wnk_den; wnk_num = (long long)(new_wnk_num % MOD); wnk_den = (long long)(new_wnk_den % MOD); long long d = gcd(wnk_num, wnk_den); wnk_num = (wnk_num / d); wnk_den = (wnk_den / d); } long long power(long long b, long long e) { if (e==0) return 1; long long half = power(b, e/2); half = (half * half) % MOD; if (e%2) return (half * b) % MOD; else return half; } long long inv(long long x) { return power(x, MOD-2); } int main() { wnk_num=0, wnk_den=1; ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<vector<int16_t>> Gens2(n, vector<int16_t>(k)); for (int i=0; i<k; i++) for (int j=0; j<n; j++) { int x; cin >> x; Gens2[x-1][i] = j; // reverse permutation } vector<vector<bool>> Visited(n, vector<bool>(n)); vector<vector<bool>> Side(n, vector<bool>(n)); queue<PosPair>Q; for (int16_t bi=0; bi<n; bi++) for (int16_t bj=bi+1; bj<n; bj++) if (!Visited[bi][bj]) { Visited[bi][bj] = true; Q.push({bi,bj}); long long cnt_no=1, cnt_o=0; bool collapse = false; while(!Q.empty()) { PosPair pp = Q.front(); Q.pop(); for (int g=0; g<k; g++) { int16_t ii = Gens2[pp.i][g]; int16_t jj = Gens2[pp.j][g]; bool rev = ii > jj; if (rev) swap(ii, jj); if (!Visited[ii][jj]) { Visited[ii][jj] = true; Side[ii][jj] = (Side[pp.i][pp.j] != rev); if (Side[ii][jj]) cnt_o++; else cnt_no++; Q.push({ii,jj}); } else if ((Side[pp.i][pp.j]!=rev) != Side[ii][jj]) collapse = true; } } /* cerr << "collapse=" << collapse << endl; */ /* cerr << "cnt_no=" << cnt_no << endl; */ /* cerr << "cnt_o=" << cnt_o << endl; */ if (collapse) add_to_wnk(cnt_o+cnt_no, 2); else add_to_wnk(2*cnt_o*cnt_no, cnt_o+cnt_no); } /* cout << "Result = " << wnk_num << " / " << wnk_den << endl; */ /* cerr << "wnk_int=" << wnk_int << endl; */ /* cerr << "wnk_num=" << wnk_num << endl; */ /* cerr << "wnk_den=" << wnk_den << endl; */ /* cerr << inv(wnk_den) << endl; */ cout << ((wnk_num * inv(wnk_den) + wnk_int) % MOD) << '\n'; return 0; } |