Submit Info #46320

Problem Lang User Status Time Memory
Hafnian of Matrix cpp KNKMT AC 5625 ms 2.54 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
large_00 AC 53 ms 1.15 MiB
large_01 AC 116 ms 1.31 MiB
large_02 AC 544 ms 1.55 MiB
max_00 AC 5618 ms 2.54 MiB
max_01 AC 5625 ms 2.47 MiB
max_02 AC 5616 ms 2.47 MiB
small_00 AC 2 ms 0.68 MiB
small_01 AC 1 ms 0.68 MiB
small_02 AC 3 ms 0.68 MiB

#include <iostream> #include<vector> #include<string> #include<algorithm> #include<iomanip> #include<map> #include<random> #include<complex> #include<math.h> #include<functional> #include<stack> #include<queue> #include<unordered_map> #include<set> #include<numeric> #include <cassert> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define req(i,n) for(int i = 1;i <= n; i++) #define rrep(i,n) for(ll i = n-1;i >= 0;i--) #define ALL(obj) begin(obj), end(obj) #define RALL(a) rbegin(a),rend(a) typedef long long ll; typedef long double ld; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int inf = 0x3fffffff; const ll INF = 1e18; template <unsigned int mod> class ModInt { private: unsigned int v; static unsigned int norm(const unsigned int& x) { return x < mod ? x : x - mod; } static ModInt make(const unsigned int& x) { ModInt m; return m.v = x, m; } static ModInt inv(const ModInt& x) { return make(inverse(x.v, mod)); } static unsigned int inverse(int a, int m) { int u[] = { a, 1, 0 }, v[] = { m, 0, 1 }, t; while (*v) { t = *u / *v; swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]); }return (u[1] % m + m) % m; } public: ModInt() : v{ 0 } {} ModInt(const long long val) : v{ norm(val % mod + mod) } {} ModInt(const ModInt<mod>& n) : v{ n() } {} explicit operator bool() const noexcept { return v != 0; } bool operator!() const noexcept { return !static_cast<bool>(*this); } ModInt& operator=(const ModInt& n) { return v = n(), (*this); } ModInt& operator=(const long long val) { return v = norm(val % mod + mod), (*this); } ModInt operator+() const { return *this; } ModInt operator-() const { return v == 0 ? make(0) : make(mod - v); } ModInt operator+(const ModInt& val) const { return make(norm(v + val())); } ModInt operator-(const ModInt& val) const { return make(norm(v + mod - val())); } ModInt operator*(const ModInt& val) const { return make((long long)v * val() % mod); } ModInt operator/(const ModInt& val) const { return *this * inv(val); } ModInt& operator+=(const ModInt& val) { return *this = *this + val; } ModInt& operator-=(const ModInt& val) { return *this = *this - val; } ModInt& operator*=(const ModInt& val) { return *this = *this * val; } ModInt& operator/=(const ModInt& val) { return *this = *this / val; } ModInt operator+(const long long val) const { return ModInt{ v + val }; } ModInt operator-(const long long val) const { return ModInt{ v - val }; } ModInt operator*(const long long val) const { return ModInt{ (long long)(v * (val % mod)) }; } ModInt operator/(const long long val) const { return ModInt{ (long long)v * inv(val) }; } ModInt& operator+=(const long long val) { return *this = *this + val; } ModInt& operator-=(const long long val) { return *this = *this - val; } ModInt& operator*=(const long long val) { return *this = *this * val; } ModInt& operator/=(const long long val) { return *this = *this / val; } bool operator==(const ModInt& val) const { return v == val.v; } bool operator!=(const ModInt& val) const { return !(*this == val); } bool operator==(const long long val) const { return v == norm(val % mod + mod); } bool operator!=(const long long val) const { return !(*this == val); } unsigned int operator()() const { return v; } friend ModInt operator+(const long long val, const ModInt& n) { return n + val; } friend ModInt operator-(const long long val, const ModInt& n) { return ModInt{ val - n() }; } friend ModInt operator*(const long long val, const ModInt& n) { return n * val; } friend ModInt operator/(const long long val, const ModInt& n) { return ModInt{ val } / n; } friend bool operator==(const long long val, const ModInt& n) { return n == val; } friend bool operator!=(const long long val, const ModInt& n) { return !(val == n); } friend istream& operator>>(istream& is, ModInt& n) { unsigned int v; return is >> v, n = v, is; } friend ostream& operator<<(ostream& os, const ModInt& n) { return (os << n()); } friend ModInt mod_pow(ModInt x, long long n) { ModInt ans = ((mod == 1) ? 0 : 1); while (n) { if (n & 1) ans *= x; x *= x, n >>= 1; }return ans; } }; template<typename T>struct Hafnian { typedef vector<T> poly; int n; Hafnian(int _n) :n(_n) {} void add(poly& f, const poly& a, const poly& b)const { rep(i,n)for (int j = 0; i + j + 1 < n; j++) { f[i + j + 1] += a[i] * b[j]; } }poly haf(vector<vector<poly>> a)const { poly res(n, 0); if (a.empty()) { res[0] = 1; return res; } const auto x = a.back(); a.pop_back(); const auto y = a.back(); a.pop_back(); int m = a.size(); const poly zero = haf(a); rep(i,n) res[i] -= zero[i]; rep(i,m) rep(j,i) { add(a[i][j], x[i], y[j]);add(a[i][j], y[i], x[j]); }const poly all = haf(a); add(res, x[m], all); rep(i,n)res[i] += all[i]; return res; } }; using mod = ModInt<998244353>; int main() { int n; cin >> n; Hafnian<mod> h(n / 2 + 1); vector<vector<vector<mod>>> a(n, vector<vector<mod>>(n, vector<mod>(n / 2 + 1))); rep(i, n) rep(j, n) cin >> a[i][j][0]; mod ans = h.haf(a).back(); cout << ans << endl; }