Submit Info #41615

Problem Lang User Status Time Memory
Hafnian of Matrix cpp eriksuenderhauf AC 1552 ms 1.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
large_00 AC 18 ms 0.78 MiB
large_01 AC 42 ms 0.91 MiB
large_02 AC 173 ms 0.92 MiB
max_00 AC 1552 ms 1.30 MiB
max_01 AC 1551 ms 1.28 MiB
max_02 AC 1552 ms 1.24 MiB
small_00 AC 1 ms 0.67 MiB
small_01 AC 1 ms 0.65 MiB
small_02 AC 3 ms 0.67 MiB

// #pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define FIO ios_base::sync_with_stdio(false); cin.tie(0); #define trav(x,a) for (auto& x: a) #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define mem(a,v) memset((a), (v), sizeof (a)) #define endl "\n" #define case(t) cout << "Case #" << (t) << ": " #define reada(a, n) for (int _i = 0; _i < (n); _i++) read(a[_i]) #define pii pair<int, int> #define pll pair<long long, long long> #define vii vector<pii> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define st first #define nd second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int mod = 998244353; const int inf = 1e9 + 7; const int N = 1e6 + 5; const double eps = 1e-9; template<class T> void read(T& x) { cin >> x; } template<class X, class Y> void read(pair<X,Y>& a) { read(a.first), read(a.second); } template<class T, size_t U> void read(array<T,U>& x) { for (int i = 0; i < U; i++) read(x[i]); } template<class T> void read(vector<T>& x) { trav(y, x) read(y); } template<class T, class... O> void read(T& x, O&... y) { read(x), read(y...); } string to_string(const char& x) { return string(1,x); } string to_string(const char*& x) { return (string)x; } string to_string(const string& x) { return x; } template<class T, class U> string to_string(const pair<T,U>& x) { return to_string(x.first) + " " + to_string(x.second); } template<class T, size_t U> string to_string(const array<T,U>& x) { string ret = ""; for (int i = 0; i < U; i++) ret += (!i ? "" : " ") + to_string(x[i]); return ret; } template<class T> string to_string(const vector<T>& x) { string ret = ""; bool f = 0; trav(y, x) ret += (!f ? "" : " ") + to_string(y), f = 1; return ret; } template<class T> string to_string(const set<T>& x) { string ret = ""; bool f = 0; trav(y, x) ret += (!f ? "" : " ") + to_string(y), f = 1; return ret; } void print() { cout << endl; } template<class T> void pr(const T& x) { cout << to_string(x); } template<class T, class... O> void print(const T& x, const O&... y) { pr(x); if (sizeof...(y)) pr(" "); print(y...); } int inv[N], ifac[N], fac[N]; inline int add(int x, int y) { return x+y < mod ? x+y : x+y-mod; } inline int sub(int x, int y) { return x-y >= 0 ? x-y : x-y+mod; } inline int mul(int x, int y) { return x * 1ll * y % mod; } template<class T, class... O> inline int add(T x, O... y) { return add(x, add(y...)); } template<class T, class... O> inline int mul(T x, O... y) { return mul(x, mul(y...)); } inline int norm(int x) { return x >= 0 ? (x < mod ? x : x-mod) : x+mod; } inline int pw(int x, int y) { int r = 1; for (; y; x = mul(x, x), y /= 2) if (y & 1) r = mul(r, x); return r; } inline int inverse(int x) { return pw(x, mod-2); } inline int ncr(int n, int k) { if (n < k || k < 0) return 0; if (n < N) return mul(fac[n], ifac[n-k], ifac[k]); int r = 1; for (int i = 1; i <= k; i++) r = mul(r, n-i+1, inv[i]); return r; } void precomputeInverse(int n) { inv[1] = ifac[0] = ifac[1] = fac[0] = fac[1] = 1; for (int i = 2; i < n; i++) { inv[i] = mod - mul(mod / i, inv[mod % i]); fac[i] = mul(fac[i-1], i); ifac[i] = mul(ifac[i-1], inv[i]); } } struct poly : vector<int> { int n; // highest coefficient x^n -> size = n + 1 poly() {} poly(int n) : n(n) { resize(n + 1); } poly operator+=(int x) { (*this)[0] = add((*this)[0], x); return *this; } poly operator+=(poly x) { for (int i = 0; i <= n; i++) (*this)[i] = add((*this)[i], x[i]); return *this; } poly operator-=(poly x) { for (int i = 0; i <= n; i++) (*this)[i] = sub((*this)[i], x[i]); return *this; } poly operator*=(poly x) { poly r(n); for (int i = 0; i <= n; i++) { unsigned long long v = 0; for (int j = 0; j <= i; j++) v += (*this)[j] * (unsigned long long)x[i - j]; r[i] = v % mod; } return (*this) = r; } poly shift() { poly r = *this; r.insert(r.begin(), 0); r.pop_back(); return r; } friend poly operator+(const int& y, poly x) { return x += y; } friend poly operator+(poly x, const int& y) { return x += y; } friend poly operator+(poly x, const poly& y) { return x += y; } friend poly operator-(poly x, const poly& y) { return x -= y; } friend poly operator*(poly x, const poly& y) { return x *= y; } void print() { for (int i = 0; i <= n; i++) cout << (*this)[i] << " "; cout << endl; } }; struct hafnian { typedef vector<vector<poly>> mat; int n; mat a; hafnian() {} hafnian(int n, vector<vector<int>>& b) : n(n) { a.resize(n); for (int i = 0; i < n; i++) { a[i].resize(i); assert(b[i][i] == 0); for (int j = 0; j < i; j++) { a[i][j] = poly(n / 2); a[i][j][0] = b[i][j]; assert(b[i][j] == b[j][i]); } } } poly solve(const mat& b) { if (!sz(b)) { poly r(n / 2); r[0] = 1; return r; } int m = sz(b); mat c = b; c.resize(m - 2); poly x = solve(c); for (int i = 0; i + 2 < m; i++) for (int j = 0; j < i; j++) { poly z = b[m-2][i] * b[m-1][j] + b[m-2][j] * b[m-1][i]; c[i][j][0] = b[i][j][0]; for (int k = 1; k <= n / 2; k++) c[i][j][k] = add(b[i][j][k], z[k-1]); // c[i][j] = b[i][j] + (b[m-2][i] * b[m-1][j] + b[m-2][j] * b[m-1][i]).shift(); } poly r(n / 2), t = solve(c); for (int i = 0; i <= n / 2; i++) { unsigned long long v = t[i]; for (int j = 0; j < i; j++) v += t[j] * (unsigned long long)b[m - 1][m - 2][i - j - 1]; r[i] = sub(v % mod, x[i]); } return r; // poly y = b[m-1][m-2]; // return solve(c) * (1 + y.shift()) - x; } int calc() { return solve(a)[n / 2]; } }; int main() { FIO srand(time(0)); int n; read(n); // chrono::duration<double> tot(0); // auto l = chrono::steady_clock::now(); vector<vector<int>> a(n); for (int i = 0; i < n; i++) a[i].resize(n); // for (int i = 0; i < n; i++) { // for (int j = i + 1; j < n; j++) { // a[i][j] = a[j][i] = rand() % 10; // } // } read(a); hafnian h(n, a); int ans = h.calc(); cout << ans << "\n"; // tot = chrono::steady_clock::now() - l; // print(tot.count()); }