QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67585#45. Tutte多项式alpha1022100 ✓5019ms118280kbC++232.9kb2022-12-10 19:17:122022-12-11 09:54:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-11 09:54:23]
  • 评测
  • 测评结果:100
  • 用时:5019ms
  • 内存:118280kb
  • [2022-12-10 19:17:12]
  • 提交

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