QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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
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...