結果
問題 | No.2445 奇行列式 |
ユーザー | Aeren |
提出日時 | 2023-08-25 23:15:42 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 16,037 bytes |
コンパイル時間 | 3,901 ms |
コンパイル使用メモリ | 372,996 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-06 18:04:42 |
合計ジャッジ時間 | 7,331 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | AC | 799 ms
5,376 KB |
ソースコード
#include <x86intrin.h> #include <bits/stdc++.h> using namespace std; #if __cplusplus > 201703L #include <ranges> using namespace numbers; #endif template<int id> struct modular_unfixed_base{ static unsigned int _mod; static unsigned long long _inverse_mod; static unsigned int &mod(){ return _mod; } static void precalc_barrett(){ _inverse_mod = (unsigned long long)-1 / _mod + 1; } static void setup(unsigned int mod = 0){ if(!mod) cin >> mod; _mod = mod; assert(_mod >= 1); precalc_barrett(); } template<class T> static vector<modular_unfixed_base> precalc_power(T base, int SZ){ vector<modular_unfixed_base> res(SZ + 1, 1); for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * base; return res; } static vector<modular_unfixed_base> _INV; static void precalc_inverse(int SZ){ if(_INV.empty()) _INV.assign(2, 1); for(auto x = _INV.size(); x <= SZ; ++ x) _INV.push_back(_mod / x * -_INV[_mod % x]); } // _mod must be a prime static modular_unfixed_base _primitive_root; static modular_unfixed_base primitive_root(){ if(_primitive_root) return _primitive_root; if(_mod == 2) return _primitive_root = 1; if(_mod == 998244353) return _primitive_root = 3; unsigned int divs[20] = {}; divs[0] = 2; int cnt = 1; unsigned int x = (_mod - 1) / 2; while(x % 2 == 0) x /= 2; for(auto i = 3; 1LL * i * i <= x; i += 2){ if(x % i == 0){ divs[cnt ++] = i; while(x % i == 0) x /= i; } } if(x > 1) divs[cnt ++] = x; for(auto g = 2; ; ++ g){ bool ok = true; for(auto i = 0; i < cnt; ++ i){ if((modular_unfixed_base(g).power((_mod - 1) / divs[i])) == 1){ ok = false; break; } } if(ok) return _primitive_root = g; } } constexpr modular_unfixed_base(): data(){ } modular_unfixed_base(const double &x){ data = normalize(llround(x)); } modular_unfixed_base(const long double &x){ data = normalize(llround(x)); } template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base(const T &x){ data = normalize(x); } template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> static unsigned int normalize(const T &x){ if(_mod == 1) return 0; assert(_inverse_mod); int sign = x >= 0 ? 1 : -1; unsigned int v = _mod <= sign * x ? sign * x - ((__uint128_t)(sign * x) * _inverse_mod >> 64) * _mod : sign * x; if(v >= _mod) v += _mod; if(sign == -1 && v) v = _mod - v; return v; } const unsigned int &operator()() const{ return data; } template<class T> operator T() const{ return data; } modular_unfixed_base &operator+=(const modular_unfixed_base &otr){ if((data += otr.data) >= _mod) data -= _mod; return *this; } modular_unfixed_base &operator-=(const modular_unfixed_base &otr){ if((data += _mod - otr.data) >= _mod) data -= _mod; return *this; } template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base &operator+=(const T &otr){ return *this += modular_unfixed_base(otr); } template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base &operator-=(const T &otr){ return *this -= modular_unfixed_base(otr); } modular_unfixed_base &operator++(){ return *this += 1; } modular_unfixed_base &operator--(){ return *this += _mod - 1; } modular_unfixed_base operator++(int){ modular_unfixed_base result(*this); *this += 1; return result; } modular_unfixed_base operator--(int){ modular_unfixed_base result(*this); *this += _mod - 1; return result; } modular_unfixed_base operator-() const{ return modular_unfixed_base(_mod - data); } modular_unfixed_base &operator*=(const modular_unfixed_base &rhs){ data = normalize((unsigned long long)data * rhs.data); return *this; } template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base &inplace_power(T e){ if(e < 0) *this = 1 / *this, e = -e; modular_unfixed_base res = 1; for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this; return *this = res; } template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base power(T e) const{ return modular_unfixed_base(*this).inplace_power(e); } modular_unfixed_base &operator/=(const modular_unfixed_base &otr){ int a = otr.data, m = _mod, u = 0, v = 1; if(a < _INV.size()) return *this *= _INV[a]; while(a){ int t = m / a; m -= t * a; swap(a, m); u -= t * v; swap(u, v); } assert(m == 1); return *this *= u; } unsigned int data; }; template<int id> unsigned int modular_unfixed_base<id>::_mod; template<int id> unsigned long long modular_unfixed_base<id>::_inverse_mod; template<int id> vector<modular_unfixed_base<id>> modular_unfixed_base<id>::_INV; template<int id> modular_unfixed_base<id> modular_unfixed_base<id>::_primitive_root; template<int id> bool operator==(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return lhs.data == rhs.data; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(const modular_unfixed_base<id> &lhs, T rhs){ return lhs == modular_unfixed_base<id>(rhs); } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(T lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) == rhs; } template<int id> bool operator!=(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return !(lhs == rhs); } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(const modular_unfixed_base<id> &lhs, T rhs){ return !(lhs == rhs); } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(T lhs, const modular_unfixed_base<id> &rhs){ return !(lhs == rhs); } template<int id> bool operator<(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return lhs.data < rhs.data; } template<int id> bool operator>(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return lhs.data > rhs.data; } template<int id> bool operator<=(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return lhs.data <= rhs.data; } template<int id> bool operator>=(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return lhs.data >= rhs.data; } template<int id> modular_unfixed_base<id> operator+(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) += rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator+(const modular_unfixed_base<id> &lhs, T rhs){ return modular_unfixed_base<id>(lhs) += rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator+(T lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) += rhs; } template<int id> modular_unfixed_base<id> operator-(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) -= rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator-(const modular_unfixed_base<id> &lhs, T rhs){ return modular_unfixed_base<id>(lhs) -= rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator-(T lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) -= rhs; } template<int id> modular_unfixed_base<id> operator*(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) *= rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator*(const modular_unfixed_base<id> &lhs, T rhs){ return modular_unfixed_base<id>(lhs) *= rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator*(T lhs, const modular_unfixed_base<id> &rhs){ return modular_unfixed_base<id>(lhs) *= rhs; } template<int id> modular_unfixed_base<id> operator/(const modular_unfixed_base<id> &lhs, const modular_unfixed_base<id> &rhs) { return modular_unfixed_base<id>(lhs) /= rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator/(const modular_unfixed_base<id> &lhs, T rhs) { return modular_unfixed_base<id>(lhs) /= rhs; } template<int id, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_unfixed_base<id> operator/(T lhs, const modular_unfixed_base<id> &rhs) { return modular_unfixed_base<id>(lhs) /= rhs; } template<int id> istream &operator>>(istream &in, modular_unfixed_base<id> &number){ long long x; in >> x; number.data = modular_unfixed_base<id>::normalize(x); return in; } // #define _PRINT_AS_FRACTION template<int id> ostream &operator<<(ostream &out, const modular_unfixed_base<id> &number){ #ifdef LOCAL #ifdef _PRINT_AS_FRACTION out << number(); cerr << "("; for(auto d = 1; ; ++ d){ if((number * d).data <= 1000000){ cerr << (number * d).data << "/" << d; break; } else if((-number * d).data <= 1000000){ cerr << "-" << (-number * d).data << "/" << d; break; } } cerr << ")"; return out; #else return out << number(); #endif #else return out << number(); #endif } #undef _PRINT_AS_FRACTION using modular = modular_unfixed_base<0>; // T must support +=, -=, *, *=, ==, and != template<class T> struct matrix{ using ring_t = T; using domain_t = vector<T>; using range_t = vector<T>; int n, m; vector<vector<T>> data; vector<T> &operator()(int i){ assert(0 <= i && i < n); return data[i]; } const vector<T> &operator()(int i) const{ assert(0 <= i && i < n); return data[i]; } T &operator()(int i, int j){ assert(0 <= i && i < n && 0 <= j && j < m); return data[i][j]; } const T &operator()(int i, int j) const{ assert(0 <= i && i < n && 0 <= j && j < m); return data[i][j]; } bool operator==(const matrix &a) const{ assert(n == a.n && m == a.m); return data == a.data; } bool operator!=(const matrix &a) const{ assert(n == a.n && m == a.m); return data != a.data; } matrix &operator+=(const matrix &a){ assert(n == a.n && m == a.m); for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] += a(i, j); return *this; } matrix operator+(const matrix &a) const{ return matrix(*this) += a; } matrix &operator-=(const matrix &a){ assert(n == a.n && m == a.m); for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] -= a(i, j); return *this; } matrix operator-(const matrix &a) const{ return matrix(*this) -= a; } matrix operator*=(const matrix &a){ assert(m == a.n); int l = a.m; matrix res(n, l); for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) for(auto k = 0; k < l; ++ k) res(i, k) += data[i][j] * a(j, k); return *this = res; } matrix operator*(const matrix &a) const{ return matrix(*this) *= a; } matrix &operator*=(T c){ for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] *= c; return *this; } matrix operator*(T c) const{ return matrix(*this) *= c; } template<class U, typename enable_if<is_integral<U>::value>::type* = nullptr> matrix &inplace_power(U e){ assert(n == m && e >= 0); matrix res(n, n, T(1)); for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this; return *this = res; } template<class U> matrix power(U e) const{ return matrix(*this).inplace_power(e); } matrix transposed() const{ matrix res(m, n); for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) res(j, i) = data[i][j]; return res; } matrix &transpose(){ return *this = transposed(); } range_t operator*(const domain_t &v) const{ assert(m == (int)v.size()); vector<T> res(n, T(0)); for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) res[i] += data[i][j] * v[j]; return res; } // Assumes T is a field // find_inverse() must return optional<T> // O(n) find_inverse() calls along with O(n^3) operations on T T determinant(auto find_inverse) const{ assert(n == m); if(n == 0) return T(1); auto a = data; T res = T(1); for(auto j = 0; j < n; ++ j){ int pivot = -1; for(auto i = j; i < n; ++ i) if(a[i][j] != T(0)){ pivot = i; break; } if(!~pivot) return T(0); swap(a[j], a[pivot]); res *= a[j][j] * (j != pivot ? -1 : 1); auto invp = find_inverse(a[j][j]); assert(invp); T inv = *invp; for(auto i = j + 1; i < n; ++ i) if(i != j && a[i][j] != T(0)){ T d = a[i][j] * inv; for(auto jj = j; jj < n; ++ jj) a[i][jj] -= d * a[j][jj]; } } return res; } // Assumes T is a field // find_inverse() must return optional<T> // O(n) find_inverse() calls along with O(n^3) operations on T optional<matrix> inverse(auto find_inverse) const{ assert(n == m); if(n == 0) return *this; auto a = data; vector<vector<T>> res(n, vector<T>(n, T(0))); for(auto i = 0; i < n; ++ i) res[i][i] = T(1); for(auto j = 0; j < n; ++ j){ int pivot = -1; for(auto i = j; i < n; ++ i) if(a[i][j] != T(0)){ pivot = i; break; } if(!~pivot) return {}; swap(a[j], a[pivot]), swap(res[j], res[pivot]); auto invp = find_inverse(a[j][j]); assert(invp); T inv = *invp; for(auto jj = 0; jj < n; ++ jj) a[j][jj] *= inv, res[j][jj] *= inv; for(auto i = 0; i < n; ++ i) if(i != j && a[i][j] != T(0)){ T d = a[i][j]; for(auto jj = 0; jj < n; ++ jj) a[i][jj] -= d * a[j][jj], res[i][jj] -= d * res[j][jj]; } } return res; } template<class output_stream> friend output_stream &operator<<(output_stream &out, const matrix &a){ out << "\n"; for(auto i = 0; i < a.n; ++ i){ for(auto j = 0; j < a.m; ++ j){ out << a(i, j) << " "; } out << "\n"; } return out; } matrix(int n, int m, T init_diagonal = T(0), T init_off_diagonal = T(0)): n(n), m(m){ data.assign(n, vector<T>(m, T(0))); for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] = i == j ? init_diagonal : init_off_diagonal; } matrix(const vector<vector<T>> &arr, int _n = -1, int _m = -1): n(~_n ? _n : (int)arr.size()), m(~_m ? _m : (int)arr[0].size()), data(arr){ } }; template<class T> matrix<T> operator*(T c, matrix<T> a){ for(auto i = 0; i < a.n; ++ i) for(auto j = 0; j < a.m; ++ j) a(i, j) = c * a(i, j); return a; } // Multiply a row vector v on the left template<class T> typename matrix<T>::domain_t operator*(const typename matrix<T>::range_t &v, const matrix<T> &a){ assert(a.n == (int)size(v)); typename matrix<T>::domain_t res(a.m, T(0)); for(auto i = 0; i < a.n; ++ i) for(auto j = 0; j < a.m; ++ j) res[j] += v[i] * a(i, j); return res; } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n, mod; cin >> n >> mod, mod <<= 1; modular::setup(mod); matrix<modular> a(n, n); for(auto i = 0; i < n; ++ i){ for(auto j = 0; j < n; ++ j){ cin >> a(i, j); } } auto det = a.determinant([&](modular x){ return x == 0 ? optional<modular>() : optional<modular>(1 / x); }); modular perm = 0; for(auto mask = 0; mask < 1 << n; ++ mask){ modular cur = 1; for(auto i = 0; i < n; ++ i){ modular sum = 0; for(auto j = 0; j < n; ++ j){ if(mask & 1 << j){ sum += a(i, j); } } cur *= sum; } if(__builtin_popcount(mask) & 1){ cur = -cur; } perm += cur; } if(n & 1){ perm = -perm; } cout << (perm - det).data / 2 << "\n"; return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////