Submit Info #41617

Problem Lang User Status Time Memory
Hafnian of Matrix cpp eriksuenderhauf AC 664 ms 1.18 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.62 MiB
large_00 AC 7 ms 0.76 MiB
large_01 AC 17 ms 0.88 MiB
large_02 AC 77 ms 1.01 MiB
max_00 AC 662 ms 1.18 MiB
max_01 AC 662 ms 1.02 MiB
max_02 AC 664 ms 1.17 MiB
small_00 AC 1 ms 0.62 MiB
small_01 AC 1 ms 0.64 MiB
small_02 AC 3 ms 0.65 MiB

#pragma GCC optimize("Ofast") #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...); } struct hafnian { 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; } typedef vector<int> poly; typedef vector<vector<poly>> mat; typedef unsigned long long ull; 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 + 1); 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 + 1); r[0] = 1; return r; } int m = sz(b); mat c = b; c.resize(m - 2); poly r = solve(c); for (int i = 0; i + 2 < m; i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < n / 2; k++) { ull v = 0; for (int l = 0; l <= k; l++) v += (ull) b[m-2][i][l] * (ull) b[m-1][j][k - l] + (ull) b[m-1][i][l] * (ull) b[m-2][j][k - l]; c[i][j][k+1] = add(v % mod, c[i][j][k+1]); } } } poly t = solve(c); for (int i = 0; i <= n / 2; i++) { ull v = t[i]; for (int j = 0; j < i; j++) v += t[j] * (ull) b[m - 1][m - 2][i - j - 1]; r[i] = sub(v % mod, r[i]); } return r; } 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()); }