QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#406993#4811. Be CarefulwxyTL 22ms36268kbC++146.5kb2024-05-07 20:49:402024-05-07 20:49:50

Judging History

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

  • [2024-05-07 20:49:50]
  • 评测
  • 测评结果:TL
  • 用时:22ms
  • 内存:36268kb
  • [2024-05-07 20:49:40]
  • 提交

answer

#include <bits/stdc++.h>

namespace Main {
  const int N = 205,B = 17,mod = 998244353;
  int n,f[N][N],s[N][N],val[1 << 14],ff[N][1 << (B + 1)],g[N],h[N][1 << 14],tmp[N][1 << 14],c[N][N],soncnt[N];
  bool leaf[N];
  std::vector<int> G[N];
  int table[1 << (B + 1)],F[20][1 << 14],GG[20][1 << 14],H[1 << 14],power[N][N];
  int lowbit(int x) {
    return x & -x;
  }
  void add(int &x,int v) {
    x += v;
    if (x >= mod)
      x -= mod;
  }
  int fpow(int a,int b) {
    int res = 1;
    for ( ; b ; b >>= 1) {
      if (b & 1)
        res = 1ll * res * a % mod;
      a = 1ll * a * a % mod;
    }
    return res;
  }
  void FMT(int f[],int n) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < (1 << n); j++)
        if (j >> i & 1)
          add(f[j],f[j ^ (1 << i)]);
  }
  void IFMT(int f[],int n) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < (1 << n); j++)
        if (j >> i & 1)
          add(f[j],mod - f[j ^ (1 << i)]);
  }
  void calc(int f[],int g[],int n) {
    for (int i = 0; i <= n; i++)
      for (int j = 0; j < (1 << n); j++)
        F[i][j] = GG[i][j] = 0;
    for (int i = 0; i < (1 << n); i++) {
      F[__builtin_popcount(i)][i] = f[i];
      GG[__builtin_popcount(i)][i] = g[i];
    }
    for (int i = 0; i < (1 << n); i++)
      H[i] = 0;
    for (int i = 0; i <= n; i++)
      for (int j = 0; i + j <= n; j++) {
        FMT(F[i],n);
        FMT(GG[i],n);
        for (int k = 0; k < (1 << n); k++)
          add(H[k],1ll * F[i][k] * GG[i][k] % mod);
      }
    IFMT(H,n);
  }
  void dfs(int x,int fa) {
    leaf[x] = true;
    for (auto v : G[x]) {
      if (v == fa)
        continue;
      leaf[x] = false;
    }
    if (leaf[x]) {
      for (int i = 0; i <= n; i++)
        f[x][i] = 1;
      for (int S = 0; S < (1 << (B + 1)); S++)
        ff[x][S] = n + 1 - (int)__builtin_popcount(S);
      s[x][0] = f[x][0];
      for (int i = 1; i <= n; i++) {
        add(s[x][i],s[x][i - 1]);
        add(s[x][i],f[x][i]);
      }
      return;
    }
    int Leafcnt = 0;
    for (auto v : G[x]) {
      if (v == fa)
        continue;
      dfs(v,x);
      if (leaf[v])
        ++ Leafcnt;
      ++ soncnt[x];
    }
    std::vector<int> a;
    for (auto v : G[x]) {
      if (v == fa)
        continue;
      if (soncnt[v] > B)
        a.push_back(v);
    }
    int m = (int)a.size();
    for (int j = 0; j <= Leafcnt; j++)
      for (int S = 0; S < (1 << m); S++)
        h[j][S] = 0;
    for (int i = 0; i < soncnt[x]; i++) {
      if (i > B) {
        for (int j = 0; j <= Leafcnt; j++)
          for (int S = 0; S < (1 << m); S++)
            tmp[j][S] = h[j][S];
        for (int j = 0; j <= Leafcnt; j++)
          for (int S = 0; S < (1 << m); S++)
            h[j][S] = 0;
        val[0] = 0;
        for (int S = 1; S < (1 << m); S++) {
          val[S] = 1ll * val[S ^ lowbit(S)] * f[a[table[lowbit(S)]]][i] % mod; 
        }
        for (int j = 0; j <= Leafcnt; j++)
          for (int k = 0; k <= j; k++) {
            calc(tmp[j - k],val,m);
            if (k != 0) {
              for (int S = 0; S < (1 << m); S++)
                add(h[j][S],1ll * c[j][k] * tmp[j - k][S] % mod);
            }
            for (int S = 0; S < (1 << m); S++)
              add(h[j][S],H[S]);
          }
      }
      g[i] = 0;
      if (i <= B) {
        for (int S = 0; S < (1 << (i + 1)); S ++) {
          int mul = 1;
          for (auto v : G[x]) {
            if (v == fa)
              continue;
            mul = 1ll * mul * ff[v][S] % mod;
          }
          if (__builtin_popcount(S) & 1)
            add(g[i],mod - mul);
          else
            add(g[i],mul);
        }
      } else {
        for (int S = 0; S < (1 << (i + 1)); S ++) {
          int base = 1,sum = 0;
          for (auto v : G[x]) {
            if (v == fa)
              continue;
            if (soncnt[v] <= B && !leaf[v])
              base = 1ll * base * ff[v][S] % mod;
          }
          val[0] = 1;
          for (int j = 0; j < m; j++) {
            val[1 << j] = 0;
            for (int k = 0; k <= B; k++) {
              if (!(S >> k & 1))
                add(val[1 << j],f[a[j]][k]);
            }
            for (int k = i + 1; k <= soncnt[a[j]]; k++) {
              add(val[1 << j],f[a[j]][k]);
            }
          }
          for (int T = 0; T < (1 << m); T++) {
            if (__builtin_popcount(T) <= 1)
              continue;
            val[T] = 1ll * val[lowbit(T)] * val[T ^ lowbit(T)] % mod;
          }
          int ban = __builtin_popcount(S);
          for (int k = 0; k <= Leafcnt; k++)
            for (int T = 0; T < (1 << m); T++) {
              int cur = base;
              cur = 1ll * cur * h[k][T] % mod;
              cur = 1ll * c[Leafcnt][k] % mod * power[n + 1 - (i - B) - ban][Leafcnt - k] % mod;
              cur = 1ll * cur * val[(1 << m) - T] % mod;
              add(sum,cur);
            }
        }
      }
    }
    g[soncnt[x]] = 0;
    for (int i = 1; i <= soncnt[x]; i++) {
      add(f[x][i],g[i - 1]);
      add(f[x][i],mod - g[i]);
    }
    f[x][0] = 1;
    for (auto v : G[x]) {
      if (v == fa)
        continue;
      int sum = 0;
      for (int i = 1; i <= (leaf[v] ? n : soncnt[v]); i++)
        add(sum,f[v][i]);
      f[x][0] = 1ll * f[x][0] * sum % mod;
    }
    for (int S = 1; S < (1 << (B + 1)); S++) 
      ff[x][S] = (ff[x][S ^ lowbit(S)] + f[x][table[lowbit(S)]]) % mod;
    int sum = 0;
    for (int i = 0; i <= soncnt[x]; i++) {
      add(sum,f[x][i]);
    }
    add(ff[x][0],sum);
    for (int S = 1; S < (1 << (B + 1)); S++) {
      ff[x][S] = mod - ff[x][S];
      add(ff[x][S],sum);
    }
    s[x][0] = f[x][0];
    for (int i = 1; i <= soncnt[x]; i++) {
      add(s[x][i],s[x][i - 1]);
      add(s[x][i],f[x][i]);
    }
  }
  void main() {
    scanf("%d",&n);
    c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      c[i][0] = c[i][i] = 1;
      for (int j = 1; j < i; j++) {
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
      }
    }
    for (int i = 1; i <= n - 1; i++) {
      int u,v;
      scanf("%d%d",&u,&v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    for (int i = 0; i <= B; i++)
      table[1 << i] = i;
    power[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= n; j++)
        power[i][j] = fpow(i,j);
    }
    dfs(1,-1);
    for (int i = 0; i <= n; i++)
      printf("%d\n",f[1][i]);
  }
}

signed main() {
  Main::main();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 18352kb

input:

5
1 2
1 3
2 4
2 5

output:

55
127
34
0
0
0

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 8ms
memory: 20152kb

input:

8
1 2
1 3
1 4
1 5
1 6
6 7
6 8

output:

69632
265534
133905
47790
12636
1944
0
0
0

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 5ms
memory: 13740kb

input:

3
1 2
2 3

output:

1
3
0
0

result:

ok 4 number(s): "1 3 0 0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 16080kb

input:

2
1 2

output:

2
1
0

result:

ok 3 number(s): "2 1 0"

Test #5:

score: 0
Accepted
time: 11ms
memory: 24512kb

input:

10
1 8
1 9
6 1
2 1
1 4
1 10
1 5
7 1
3 1

output:

1755647
612579511
359376750
200038110
104287680
49974120
21379680
7771680
2177280
362880
0

result:

ok 11 numbers

Test #6:

score: 0
Accepted
time: 7ms
memory: 23340kb

input:

10
2 8
2 9
6 2
2 1
2 4
2 10
2 5
7 2
3 2

output:

114358881
100000000
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #7:

score: 0
Accepted
time: 14ms
memory: 22304kb

input:

10
7 8
8 9
6 5
2 1
3 4
9 10
4 5
7 6
3 2

output:

10
1
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 12ms
memory: 20120kb

input:

10
3 6
2 4
4 9
8 4
2 5
10 5
3 7
2 1
1 3

output:

27510
31142
102399
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #9:

score: 0
Accepted
time: 7ms
memory: 26588kb

input:

14
10 3
6 2
2 8
3 13
1 3
1 2
3 14
4 2
9 3
12 3
2 5
7 2
11 3

output:

930962871
780146137
253920328
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Test #10:

score: 0
Accepted
time: 14ms
memory: 32504kb

input:

20
7 6
2 6
5 1
17 12
9 13
12 18
3 2
9 1
2 1
12 6
10 9
14 2
4 1
6 8
11 2
16 9
13 19
8 15
20 5

output:

572808214
694156482
763085092
958730326
465749894
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 21 numbers

Test #11:

score: 0
Accepted
time: 15ms
memory: 34796kb

input:

21
6 12
11 13
1 7
8 14
1 18
5 4
1 2
16 11
21 1
9 10
15 17
1 9
1 8
1 20
1 3
1 4
19 16
11 1
15 10
3 6

output:

778184256
242901486
277265229
855621813
564317020
918444623
408876720
314039448
593931360
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 22 numbers

Test #12:

score: 0
Accepted
time: 15ms
memory: 34776kb

input:

22
20 21
9 12
6 10
19 10
16 10
10 11
8 7
13 12
21 22
19 20
14 13
7 6
8 9
15 14
2 5
18 6
5 6
3 2
16 17
2 1
3 4

output:

142157709
5878180
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 23 numbers

Test #13:

score: 0
Accepted
time: 15ms
memory: 35660kb

input:

23
6 10
4 2
6 9
15 20
10 15
3 6
17 23
1 3
16 22
19 14
17 12
7 11
18 13
11 16
5 3
8 5
10 14
8 12
9 13
4 7
1 2
15 21

output:

7619809
175546557
7936610
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 24 numbers

Test #14:

score: 0
Accepted
time: 22ms
memory: 36268kb

input:

24
7 10
2 5
2 1
17 20
1 4
16 13
7 4
19 16
23 20
11 8
10 13
1 3
22 19
5 8
3 6
17 14
21 18
24 21
18 15
9 6
9 12
14 11
15 12

output:

24
576
15025
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #15:

score: 0
Accepted
time: 15ms
memory: 36260kb

input:

24
22 16
17 11
15 9
13 7
8 2
1 3
5 1
6 12
9 3
14 8
21 15
17 23
19 13
7 1
24 18
2 1
5 11
1 4
4 10
18 12
20 14
10 16
1 6

output:

24
7962624
236177977
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #16:

score: -100
Time Limit Exceeded

input:

200
1 199
95 1
1 75
177 1
66 1
157 1
85 1
1 193
1 26
8 1
38 1
151 1
1 56
63 1
1 138
1 59
190 1
1 36
1 120
156 1
115 1
1 118
171 1
6 1
113 1
20 1
83 1
1 176
33 1
153 1
1 169
22 1
1 159
1 27
87 1
1 129
1 44
174 1
1 93
77 1
1 122
1 125
1 23
1 81
112 1
173 1
1 51
32 1
96 1
184 1
116 1
67 1
1 94
1 104
19...

output:


result: