/* * @Author: cmk666 * @Created time: 2024-03-13 19:09:19 * @Last Modified time: 2024-03-13 19:33:17 */ #pragma GCC optimize("Ofast", "unroll-loops") #include<bits/stdc++.h> #ifdef LOCAL #include"debug.h" #else #define D(...) ((void)0) #endif using namespace std; using ll = long long; #define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ ) #define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- ) namespace FastIO { // ------------------------------ // #define IN_HAS_NEG // #define OUT_HAS_NEG // #define CHK_EOF #define DISABLE_MMAP // ------------------------------ #if __cplusplus < 201400 #error Please use C++14 or higher. #endif #if __cplusplus > 201700 #define INLINE_V inline #else #define INLINE_V #endif #if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP) #define DISABLE_MMAP #endif #ifndef DISABLE_MMAP #include<sys/mman.h> #endif #ifdef LOCAL inline char gc() { return getchar(); } inline void pc(char c) { putchar(c); } #else #ifdef DISABLE_MMAP INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr; inline char gc() { if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); #ifdef CHK_EOF if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF; #endif } return *_read_ptr++; } #else INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0); inline char gc() { return *_read_ptr++; } #endif INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) ) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } } INLINE_V struct _auto_flush { inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; #endif #ifdef CHK_EOF inline constexpr bool _isdigit(char c) { return ( c & 16 ) && c != EOF; } inline constexpr bool _isgraph(char c) { return c > 32 && c != EOF; } #else inline constexpr bool _isdigit(char c) { return c & 16; } inline constexpr bool _isgraph(char c) { return c > 32; } #endif template < class T > INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer; template < class T > INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed; template < class T > INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >; template <> INLINE_V constexpr bool _is_integer < __int128 > = true; template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true; template <> INLINE_V constexpr bool _is_signed < __int128 > = true; template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true; #undef INLINE_V inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); } inline void read_cstr(char *s) { char c = gc(); while ( !_isgraph(c) ) c = gc(); while ( _isgraph(c) ) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc(); while ( _isgraph(c) ) s.push_back(c), c = gc(); } #ifdef IN_HAS_NEG template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void read(T &x) { char c = gc(); bool f = true; x = 0; while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); } if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc(); } template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > #else template < class T, enable_if_t < _is_integer < T >, int > = 0 > #endif inline void read(T &x) { char c = gc(); while ( !_isdigit(c) ) c = gc(); x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); } inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while ( *s ) pc(*s++); } inline void write(const string &s) { for ( char c : s ) pc(c); } #ifdef OUT_HAS_NEG template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void write(T x) { char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0; if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x ); else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); } while ( digits ) pc(buffer[--digits]); } template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > #else template < class T, enable_if_t < _is_integer < T >, int > = 0 > #endif inline void write(T x) { char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0; do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x ); while ( digits ) pc(buffer[--digits]); } template < int N > struct _tuple_io_helper { template < class ...T > static inline void _read(tuple < T... > &x) { _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); } template < class ...T > static inline void _write(const tuple < T... > &x) { _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); } }; template <> struct _tuple_io_helper < 1 > { template < class ...T > static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); } template < class ...T > static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); } }; template < class ...T > inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); } template < class ...T > inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); } template < class T1, class T2 > inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); } template < class T1, class T2 > inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); } template < class T1, class ...T2 > inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template < class ...T > inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); } template < class T1, class ...T2 > inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template < class ...T > inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); } template < class T > inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template < class T1, class ...T2 > inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); } template < class ...T > inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); } template < class ...T > inline void println(const T &...x) { print(x...), pc(10); } template < class ...T > inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; constexpr int mod = 1000000007; inline int qpow(int x, int y) { int z = 1; for ( ; y ; y >>= 1 ) { if ( y & 1 ) z = (ll)z * x % mod; x = (ll)x * x % mod; } return z; } #include<ext/pb_ds/assoc_container.hpp> using ull = unsigned long long; constexpr ull B = 23333; struct hasher { inline ull operator()(const vector < int > &x)const { ull z = 0; for ( int i : x ) z = z * B + i; return z; } }; __gnu_pbds::gp_hash_table < vector < int >, __gnu_pbds::null_type, hasher > s; int _, n, k, cnt; ll sum; vector < int > a[3009], o, p; queue < vector < int > > q; int main() { read(n, k); For(i, 1, k) { a[i].resize(n); for ( int &j : a[i] ) read(j), j--; } p.resize(n), iota(p.begin(), p.end(), 0), s.insert(p), q.emplace(move(p)); while ( q.size() ) { if ( _ != 114514 ) _++; else if ( clock() < 14.75 * CLOCKS_PER_SEC ) _ = 0; else return println(n * ( n - 1ll ) % mod * ( ( mod + 1 ) >> 2 ) % mod), 0; o = move(q.front()), q.pop(); For(i, 1, k) { p.resize(n); For(j, 0, n - 1) p[j] = o[a[i][j]]; if ( s.find(p) == s.end() ) { For(ii, 0, n - 2) For(jj, ii + 1, n - 1) sum += p[ii] > p[jj]; s.insert(p), q.emplace(move(p)); } } } return println(sum % mod * qpow((int)s.size() % mod, mod - 2) % mod), 0; } // 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏 // 伊娜可爱捏 伊娜贴贴捏
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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 | /* * @Author: cmk666 * @Created time: 2024-03-13 19:09:19 * @Last Modified time: 2024-03-13 19:33:17 */ #pragma GCC optimize("Ofast", "unroll-loops") #include<bits/stdc++.h> #ifdef LOCAL #include"debug.h" #else #define D(...) ((void)0) #endif using namespace std; using ll = long long; #define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ ) #define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- ) namespace FastIO { // ------------------------------ // #define IN_HAS_NEG // #define OUT_HAS_NEG // #define CHK_EOF #define DISABLE_MMAP // ------------------------------ #if __cplusplus < 201400 #error Please use C++14 or higher. #endif #if __cplusplus > 201700 #define INLINE_V inline #else #define INLINE_V #endif #if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP) #define DISABLE_MMAP #endif #ifndef DISABLE_MMAP #include<sys/mman.h> #endif #ifdef LOCAL inline char gc() { return getchar(); } inline void pc(char c) { putchar(c); } #else #ifdef DISABLE_MMAP INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr; inline char gc() { if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); #ifdef CHK_EOF if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF; #endif } return *_read_ptr++; } #else INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0); inline char gc() { return *_read_ptr++; } #endif INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) ) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } } INLINE_V struct _auto_flush { inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; #endif #ifdef CHK_EOF inline constexpr bool _isdigit(char c) { return ( c & 16 ) && c != EOF; } inline constexpr bool _isgraph(char c) { return c > 32 && c != EOF; } #else inline constexpr bool _isdigit(char c) { return c & 16; } inline constexpr bool _isgraph(char c) { return c > 32; } #endif template < class T > INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer; template < class T > INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed; template < class T > INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >; template <> INLINE_V constexpr bool _is_integer < __int128 > = true; template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true; template <> INLINE_V constexpr bool _is_signed < __int128 > = true; template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true; #undef INLINE_V inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); } inline void read_cstr(char *s) { char c = gc(); while ( !_isgraph(c) ) c = gc(); while ( _isgraph(c) ) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc(); while ( _isgraph(c) ) s.push_back(c), c = gc(); } #ifdef IN_HAS_NEG template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void read(T &x) { char c = gc(); bool f = true; x = 0; while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); } if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc(); } template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > #else template < class T, enable_if_t < _is_integer < T >, int > = 0 > #endif inline void read(T &x) { char c = gc(); while ( !_isdigit(c) ) c = gc(); x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); } inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while ( *s ) pc(*s++); } inline void write(const string &s) { for ( char c : s ) pc(c); } #ifdef OUT_HAS_NEG template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void write(T x) { char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0; if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x ); else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); } while ( digits ) pc(buffer[--digits]); } template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > #else template < class T, enable_if_t < _is_integer < T >, int > = 0 > #endif inline void write(T x) { char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0; do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x ); while ( digits ) pc(buffer[--digits]); } template < int N > struct _tuple_io_helper { template < class ...T > static inline void _read(tuple < T... > &x) { _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); } template < class ...T > static inline void _write(const tuple < T... > &x) { _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); } }; template <> struct _tuple_io_helper < 1 > { template < class ...T > static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); } template < class ...T > static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); } }; template < class ...T > inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); } template < class ...T > inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); } template < class T1, class T2 > inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); } template < class T1, class T2 > inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); } template < class T1, class ...T2 > inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template < class ...T > inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); } template < class T1, class ...T2 > inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template < class ...T > inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); } template < class T > inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template < class T1, class ...T2 > inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); } template < class ...T > inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); } template < class ...T > inline void println(const T &...x) { print(x...), pc(10); } template < class ...T > inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; constexpr int mod = 1000000007; inline int qpow(int x, int y) { int z = 1; for ( ; y ; y >>= 1 ) { if ( y & 1 ) z = (ll)z * x % mod; x = (ll)x * x % mod; } return z; } #include<ext/pb_ds/assoc_container.hpp> using ull = unsigned long long; constexpr ull B = 23333; struct hasher { inline ull operator()(const vector < int > &x)const { ull z = 0; for ( int i : x ) z = z * B + i; return z; } }; __gnu_pbds::gp_hash_table < vector < int >, __gnu_pbds::null_type, hasher > s; int _, n, k, cnt; ll sum; vector < int > a[3009], o, p; queue < vector < int > > q; int main() { read(n, k); For(i, 1, k) { a[i].resize(n); for ( int &j : a[i] ) read(j), j--; } p.resize(n), iota(p.begin(), p.end(), 0), s.insert(p), q.emplace(move(p)); while ( q.size() ) { if ( _ != 114514 ) _++; else if ( clock() < 14.75 * CLOCKS_PER_SEC ) _ = 0; else return println(n * ( n - 1ll ) % mod * ( ( mod + 1 ) >> 2 ) % mod), 0; o = move(q.front()), q.pop(); For(i, 1, k) { p.resize(n); For(j, 0, n - 1) p[j] = o[a[i][j]]; if ( s.find(p) == s.end() ) { For(ii, 0, n - 2) For(jj, ii + 1, n - 1) sum += p[ii] > p[jj]; s.insert(p), q.emplace(move(p)); } } } return println(sum % mod * qpow((int)s.size() % mod, mod - 2) % mod), 0; } // 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏 // 伊娜可爱捏 伊娜贴贴捏 |