Submit Info #9224

Problem Lang User Status Time Memory
Hafnian of Matrix cpp chocorusk AC 8712 ms 198.43 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
large_00 AC 53 ms 3.11 MiB
large_01 AC 122 ms 5.83 MiB
large_02 AC 679 ms 23.33 MiB
max_00 AC 8712 ms 198.43 MiB
max_01 AC 8710 ms 198.36 MiB
max_02 AC 8684 ms 198.37 MiB
small_00 AC 1 ms 0.67 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 0 ms 0.80 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll MOD=998244353; vector<ll> subset_convolution(int n, vector<ll> a, vector<ll> b){ vector<ll> ret(1<<n); vector<vector<ll>> dpa(n+1, vector<ll>(1<<n)), dpb(n+1, vector<ll>(1<<n)); for(int i=0; i<(1<<n); i++){ dpa[popcount(i)][i]=a[i], dpb[popcount(i)][i]=b[i]; } for(int k=0; k<=n; k++){ for(int i=0; i<n; i++){ for(int j=0; j<(1<<n); j++){ if(!(j&(1<<i))){ dpa[k][j^(1<<i)]+=dpa[k][j]; if(dpa[k][j^(1<<i)]>=MOD) dpa[k][j^(1<<i)]-=MOD; dpb[k][j^(1<<i)]+=dpb[k][j]; if(dpb[k][j^(1<<i)]>=MOD) dpb[k][j^(1<<i)]-=MOD; } } } } for(int i=0; i<(1<<n); i++){ for(int j=n; j>=0; j--){ for(int k=1; k<=n-j; k++) (dpa[j+k][i]+=dpa[j][i]*dpb[k][i])%=MOD; (dpa[j][i]*=dpb[0][i])%=MOD; } } for(int k=0; k<=n; k++){ for(int i=0; i<n; i++){ for(int j=0; j<(1<<n); j++){ if(!(j&(1<<i))){ dpa[k][j^(1<<i)]+=MOD-dpa[k][j]; if(dpa[k][j^(1<<i)]>=MOD) dpa[k][j^(1<<i)]-=MOD; } } } } for(int i=0; i<(1<<n); i++) ret[i]=dpa[popcount(i)][i]; return ret; } vector<ll> add(vector<ll> a, vector<ll> b){ vector<ll> ret(a.size()); for(int i=0; i<a.size(); i++){ ret[i]=a[i]+b[i]; if(ret[i]>=MOD) ret[i]-=MOD; } return ret; } ll hafnian(vector<vector<ll>> a){ int n=a.size()/2; vector<ll> h(1, 1); vector<vector<vector<ll>>> b(2*n, vector<vector<ll>>(2*n, vector<ll>(1))); for(int i=0; i<2*n; i++) for(int j=0; j<2*n; j++) b[i][j][0]=a[i][j]; for(int i=1; i<=n; i++){ vector<ll> c(1<<i); c[0]=1; for(int j=0; j<(1<<(i-1)); j++){ c[j^(1<<(i-1))]=b[0][1][j]; } h.resize(1<<i); h=subset_convolution(i, h, c); if(i==n) break; vector<vector<vector<ll>>> b2(2*(n-i), vector<vector<ll>>(2*(n-i))); for(int j=0; j<2*(n-i); j++){ for(int k=0; k<2*(n-i); k++){ if(j==k){ b2[j][k].resize(1<<i); continue; } b2[j][k]=b[j+2][k+2]; b2[j][k].resize(1<<i); vector<ll> s=add(subset_convolution(i-1, b[0][j+2], b[1][k+2]), subset_convolution(i-1, b[1][j+2], b[0][k+2])); for(int l=0; l<s.size(); l++){ b2[j][k][l^(1<<(i-1))]+=s[l]; if(b2[j][k][l^(1<<(i-1))]>=MOD) b2[j][k][l^(1<<(i-1))]-=MOD; } } } swap(b, b2); } return h[(1<<n)-1]; } int main() { int n; scanf("%d", &n); vector<vector<ll>> a(n, vector<ll>(n)); for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%lld", &a[i][j]); printf("%lld\n", hafnian(a)); return 0; }