QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#67585 | #45. Tutte多项式 | alpha1022 | 100 ✓ | 5019ms | 118280kb | C++23 | 2.9kb | 2022-12-10 19:17:12 | 2022-12-11 09:54:23 |
Judging History
answer
#include <bits/stdc++.h>
#define popcnt __builtin_popcount
using namespace std;
using ll = long long;
using L = __int128_t;
const int mod = 998244353;
void add(int &x, int y) { if ((x += y - mod) < 0) x += mod; }
void sub(int &x, int y) { if ((x -= y) < 0) x += mod; }
int mpow(int a, int b) {
int ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret = (ll)ret * a % mod;
a = (ll)a * a % mod;
}
return ret;
}
const int LG = 21;
const int N = 1 << LG;
int lg, n;
int e[LG + 1];
int f[N], g[N], t[N];
int x, y;
namespace Set {
int fac[LG + 1], ifac[LG + 1], inv[LG + 1];
void init() {
fac[0] = 1;
for (int i = 1; i <= LG; ++i) fac[i] = (ll)fac[i - 1] * i % mod;
ifac[LG] = mpow(fac[LG], mod - 2);
for (int i = LG; i; --i) ifac[i - 1] = (ll)ifac[i] * i % mod;
for (int i = 1; i <= LG; ++i) inv[i] = (ll)ifac[i] * fac[i - 1] % mod;
}
template<class T>
void fmt(T a, int lg, int type) {
auto func = type == 1 ? add : sub;
for (int w = 2, m = 1; w <= (1 << lg); w <<= 1, m <<= 1)
for (int i = 0; i < (1 << lg); i += w)
for (int j = 0; j < m; ++j)
for (int k = 0; k <= lg; ++k)
func(a[i | j | m][k], a[i | j][k]);
}
int t1[N][LG + 1];
void exp(int *g, int *h, int lg) {
int n = 1 << lg;
for (int i = 0; i < n; ++i) memset(t1[i], 0, sizeof(int) * (lg + 1));
for (int i = 0; i < n; ++i) t1[i][popcnt(i)] = g[i];
fmt(t1, lg, 1);
for (int s = 0; s < n; ++s) {
static int tt[LG + 1];
memcpy(tt, t1[s], sizeof tt);
t1[s][0] = 1;
for (int i = 1; i <= lg; ++i) {
L v = 0;
for (int j = 1; j <= i; ++j)
v += (L)tt[j] * j * t1[s][i - j];
t1[s][i] = (ll)(v % mod) * inv[i] % mod;
}
}
fmt(t1, lg, -1);
for (int i = 0; i < n; ++i) h[i] = t1[i][popcnt(i)];
}
}
int vis[LG + 1], crit[N], coe[LG + 1];
void dfs(int p) {
vis[p] = 1;
for (int i = 0; i < lg; ++i)
if (((e[p] >> i) & 1) && !vis[i])
dfs(i);
}
int main() {
Set::init();
scanf("%d", &lg), n = 1 << lg;
for (int i = 0; i < lg; ++i)
for (int j = 0; j < lg; ++j) {
int x;
scanf("%d", &x), e[i] |= x << j;
}
scanf("%d%d", &x, &y), sub(x, 1);
for (int i = 0; i < lg; ++i)
if (!vis[i]) {
dfs(i);
for (int s = 0; s < n; ++s)
if ((s >> i) & 1)
crit[s] = 1;
}
for (int i = 1; i <= lg; ++i)
coe[i] = ((ll)coe[i - 1] * y + 1) % mod;
for (int i = 0; i < lg; ++i) {
for (int s = 0; s < (1 << i); ++s)
t[s] = (ll)g[s] * coe[popcnt(e[i] & s)] % mod;
Set::exp(t, g + (1 << i), i);
}
for (int s = 1; s < n; ++s)
if (!crit[s]) g[s] = (ll)g[s] * x % mod;
Set::exp(g, f, lg - 1);
L ans = 0;
for (int s = 0; s < (1 << (lg - 1)); ++s)
ans += (ll)g[(n - 1) ^ s] * f[s];
printf("%d\n", (int)(ans % mod));
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 16
Accepted
Test #1:
score: 16
Accepted
time: 0ms
memory: 3600kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1
output:
6
result:
ok answer is 6
Test #2:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 2
output:
24
result:
ok answer is 24
Test #3:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
output:
10
result:
ok answer is 10
Test #4:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1
output:
24
result:
ok answer is 24
Test #5:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 2
output:
52
result:
ok answer is 52
Test #6:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 2 0
output:
60
result:
ok answer is 60
Test #7:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 2 1
output:
86
result:
ok answer is 86
Test #8:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1
output:
3
result:
ok answer is 3
Test #9:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 20020221
output:
20020223
result:
ok answer is 20020223
Test #10:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 20020814 1
output:
807453860
result:
ok answer is 807453860
Test #11:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 20020814 20020221
output:
307912635
result:
ok answer is 307912635
Test #12:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1
output:
24
result:
ok answer is 24
Test #13:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 20020221
output:
98439924
result:
ok answer is 98439924
Test #14:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 20020814 1
output:
705719054
result:
ok answer is 705719054
Test #15:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 20020814 20020221
output:
485607933
result:
ok answer is 485607933
Test #16:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
7 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1
output:
48
result:
ok answer is 48
Test #17:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
7 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 20020221
output:
815810322
result:
ok answer is 815810322
Test #18:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
7 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 20020814 1
output:
387261289
result:
ok answer is 387261289
Test #19:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
7 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 20020814 20020221
output:
895603904
result:
ok answer is 895603904
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #20:
score: 20
Accepted
time: 4ms
memory: 3660kb
input:
11 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 20020221
output:
153595675
result:
ok answer is 153595675
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
11 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 20020814 1
output:
491253731
result:
ok answer is 491253731
Test #22:
score: 0
Accepted
time: 4ms
memory: 3660kb
input:
11 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 20020814 20020221
output:
17689848
result:
ok answer is 17689848
Subtask #3:
score: 14
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #23:
score: 14
Accepted
time: 19ms
memory: 4436kb
input:
14 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0...
output:
171192566
result:
ok answer is 171192566
Test #24:
score: 0
Accepted
time: 20ms
memory: 4588kb
input:
14 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0...
output:
858770596
result:
ok answer is 858770596
Test #25:
score: 0
Accepted
time: 19ms
memory: 4676kb
input:
14 0 0 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1...
output:
220200163
result:
ok answer is 220200163
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #26:
score: 25
Accepted
time: 424ms
memory: 17896kb
input:
18 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0...
output:
150803960
result:
ok answer is 150803960
Test #27:
score: 0
Accepted
time: 424ms
memory: 17880kb
input:
18 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1...
output:
295845902
result:
ok answer is 295845902
Test #28:
score: 0
Accepted
time: 434ms
memory: 17960kb
input:
18 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1...
output:
82075728
result:
ok answer is 82075728
Subtask #5:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #29:
score: 25
Accepted
time: 5008ms
memory: 118212kb
input:
21 0 0 0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0...
output:
794685740
result:
ok answer is 794685740
Test #30:
score: 0
Accepted
time: 4944ms
memory: 118208kb
input:
21 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1...
output:
584501085
result:
ok answer is 584501085
Test #31:
score: 0
Accepted
time: 5019ms
memory: 118280kb
input:
21 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0...
output:
114086868
result:
ok answer is 114086868