Submit Info #45318

Problem Lang User Status Time Memory
Hafnian of Matrix cpp Elegia AC 2864 ms 109.46 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
large_00 AC 23 ms 2.35 MiB
large_01 AC 50 ms 4.08 MiB
large_02 AC 256 ms 14.24 MiB
max_00 AC 2856 ms 109.38 MiB
max_01 AC 2862 ms 109.46 MiB
max_02 AC 2864 ms 109.43 MiB
small_00 AC 1 ms 0.68 MiB
small_01 AC 1 ms 0.74 MiB
small_02 AC 0 ms 0.78 MiB

#include <bits/stdc++.h> #define popcnt __builtin_popcount using namespace std; typedef long long ll; typedef unsigned long long ull; const int P = 998244353; int norm(int x) { return x >= P ? (x - P) : x; } int quo2(int x) { return (x + ((x & 1) ? P : 0)) >> 1; } void add(int &x, int y) { if ((x += y - P) < 0) x += P; } void ad(int &x, int y) { x += y; } void sub(int &x, int y) { if ((x -= y) < 0) x += P; } void exGcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return; } exGcd(b, a % b, y, x); y -= a / b * x; } int inv(int a) { int x, y; exGcd(a, P, x, y); return norm(x + P); } namespace SET { const int N = 20; #define TRANSFORM(V, OP, Tr_n) \ do { \ for (int Tr_i = 0; Tr_i != Tr_n; ++Tr_i) \ for (int Tr_s = 0; Tr_s != 1 << Tr_n; ++Tr_s) \ if ((Tr_s >> Tr_i) & 1) \ for (int Tr_j = 0; Tr_j <= Tr_n; ++Tr_j) \ OP(V[Tr_s][Tr_j], V[Tr_s ^ 1 << Tr_i][Tr_j]);\ } while(false) #define TTRANSFORM(V, OP, Tr_n) \ do { \ for (int Tr_i = 0; Tr_i != Tr_n; ++Tr_i) \ for (int Tr_s = 0; Tr_s != 1 << Tr_n; ++Tr_s) \ if ((Tr_s >> Tr_i) & 1) \ for (int Tr_j = 0; Tr_j <= Tr_n; ++Tr_j) \ OP(V[Tr_s ^ 1 << Tr_i][Tr_j], V[Tr_s][Tr_j]);\ } while(false) void convT(int *a, int *b, int *c, int n) { static int f[1 << N][N + 1], g[1 << N][N + 1]; for (int i = 0; i != 1 << n; ++i) { fill_n(f[i], n + 1, 0); fill_n(g[i], n + 1, 0); f[i][popcnt(i)] = a[i]; g[i][popcnt(i)] = b[i]; } TTRANSFORM(f, sub, n); TRANSFORM(g, add, n); for (int i = 0; i != 1 << n; ++i) for (int j = 0; j <= n; ++j) { ull v = 0; for (int k = 0; k <= n - j; ++k) v += f[i][j + k] * (ull) g[i][k]; f[i][j] = v % P; } TTRANSFORM(f, add, n); for (int i = 0; i != 1 << n; ++i) add(c[i], f[i][popcnt(i)]); } } const int N = 40, N2 = N / 2; namespace COUNT_MATCH { int g[N][N]; int dp[1 << N2][N]; int x[1 << N2], y[1 << N2], z[1 << N2], tmp[1 << N2]; void main(int n) { if (n & 1) ++n; int n2 = n / 2; for (int s = 1; s != 1 << n2; ++s) for (int i = 0; i != n; ++i) { if (!((s >> (i >> 1)) & 1)) continue; if (!(s & (s - 1))) dp[s][i] = 1; else for (int j = 0; j != n; ++j) dp[s][i] = (dp[s][i] + g[i ^ 1][j] * (ull)dp[s ^ (1 << (i >> 1))][j]) % P; add(x[s], dp[s][i]); } for (int s = 0; s != 1 << n2; ++s) x[s] = quo2(x[s]); for (int u = 0; u != n; u += 2) { memset(dp, 0, sizeof(int) * N << (u >> 1)); dp[0][u] = 1; for (int s = 0; s != 1 << (u >> 1); ++s) for (int i = 0; i != n; ++i) { if ((s >> (i >> 1)) & 1) for (int j = 0; j != n; ++j) dp[s][i] = (dp[s][i] + g[i ^ 1][j] * (ull)dp[s ^ (1 << (i >> 1))][j]) % P; y[s | (1 << (u >> 1))] = (y[s | (1 << (u >> 1))] + g[i][u ^ 1] * (ull)dp[s][i]) % P; } } memcpy(z, y + (1 << (n2 - 1)), sizeof(int) << (n2 - 1)); reverse(z, z + (1 << (n2 - 1))); memcpy(z + (1 << (n2 - 1)), x + (1 << (n2 - 1)), sizeof(int) << (n2 - 1)); reverse(z + (1 << (n2 - 1)), z + (1 << n2)); for (int i = n2 - 2; i >= 0; --i) { memset(tmp, 0, sizeof(int) * (n2 - i + 1) << i); for (int j = 0; j < n2 - i; ++j) { SET::convT(z + ((j * 2 + 1) << i), x + (1 << i), tmp + ((j + 1) << i), i); SET::convT(z + ((j * 2 + 1) << i), y + (1 << i), tmp + (j << i), i); } for (int j = 1; j < n2 - i; ++j) memcpy(z + (j << i), z + ((j * 2) << i), sizeof(int) << i); memset(z + ((n2 - i) << i), 0, sizeof(int) << i); for (int j = 0; j != (n2 - i + 1) << i; ++j) add(z[j], tmp[j]); } reverse(z, z + n2 + 1); } } int n; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i != n; ++i) for (int j = 0; j != n; ++j) cin >> COUNT_MATCH::g[i][j]; COUNT_MATCH::main(n); cout << COUNT_MATCH::z[n / 2] << '\n'; return 0; }