QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#406993	#4811. Be Careful	wxy	TL	22ms	36268kb	C++14	6.5kb	2024-05-07 20:49:40	2024-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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 18352kb

input:

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 8ms

memory: 20152kb

input:

output:

result:

ok 9 numbers

Test #3:

score: 0

Accepted

time: 5ms

memory: 13740kb

input:

3
1 2
2 3

output:

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:

output:

result:

ok 11 numbers

Test #6:

score: 0

Accepted

time: 7ms

memory: 23340kb

input:

output:

result:

ok 11 numbers

Test #7:

score: 0

Accepted

time: 14ms

memory: 22304kb

input:

output:

result:

ok 11 numbers

Test #8:

score: 0

Accepted

time: 12ms

memory: 20120kb

input:

output:

result:

ok 11 numbers

Test #9:

score: 0

Accepted

time: 7ms

memory: 26588kb

input:

output:

result:

ok 15 numbers

Test #10:

score: 0

Accepted

time: 14ms

memory: 32504kb

input:

output:

result:

ok 21 numbers

Test #11:

score: 0

Accepted

time: 15ms

memory: 34796kb

input:

output:

result:

ok 22 numbers

Test #12:

score: 0

Accepted

time: 15ms

memory: 34776kb

input:

output:

result:

ok 23 numbers

Test #13:

score: 0

Accepted

time: 15ms

memory: 35660kb

input:

output:

result:

ok 24 numbers

Test #14:

score: 0

Accepted

time: 22ms

memory: 36268kb

input:

output:

result:

ok 25 numbers

Test #15:

score: 0

Accepted

time: 15ms

memory: 36260kb

input:

output:

result:

ok 25 numbers

Test #16:

score: -100

Time Limit Exceeded

input: