QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#78578 | #4811. Be Careful | huzhaoyang | WA | 4ms | 46664kb | C++14 | 3.4kb | 2023-02-19 16:19:49 | 2023-02-19 16:19:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205,M=19,mod=998244353;
int n,K,x,y,d[N],l[N],t[N],pw[N],C[N][N];
int fs[N],f[N][N],h[1<<M],sum[N][1<<M],g[N][1<<M],g0[N][1<<M];
vector<int>v,e[N];
int lowbit(int k){
return (k&(-k));
}
int add(int x,int y){
x+=y;
return (x<mod ? x : x-mod);
}
void dfs(int k,int fa){
for(int son:e[k])
if (son!=fa){
dfs(son,k),d[k]++;
if (!d[son])l[k]++;
}
if (!d[k]){
for(int i=0;i<=n;i++)f[k][i]=1;
return;
}
int K=0;
// int K=0,mn=d[k]-l[k];
// for(int i=1;i<=d[k];i++){
// int s=i;
// for(int son:e[k])
// if ((son!=fa)&&(d[son]>i))s++;
// if (mn>s)K=i,mn=s;
// }
v.clear();
for(int son:e[k])
if ((son!=fa)&&(d[son]>K))v.push_back(son);
t[k]=v.size();
for(int son:e[k])
if (son!=fa){
for(int i=0;i<=K;i++)sum[son][1<<i]=f[son][i];
for(int T=1;T<(1<<K+1);T++){
int T0=(T&(-T));
sum[son][T]=add(sum[son][T0],sum[son][T^T0]);
}
}
for(int son:e[k])
if (son!=fa){
for(int i=K+1;i<=n;i++)fs[son]=add(fs[son],f[son][i]);
}
for(int i=K;i>=0;i--){
for(int T=0;T<(1<<i);T++){
int s=(i-__builtin_popcount(T)&1 ? mod-1 : 1);
for(int son:e[k])
if (son!=fa)s=(ll)s*(fs[son]+sum[son][T])%mod;
f[k][i]=add(f[k][i],s);
}
for(int son:e[k])
if (son!=fa)fs[son]=add(fs[son],f[son][i]);
}
if (K==d[k])return;
for(int i=0;i<=l[k];i++)
for(int S=0;S<(1<<t[k]);S++)g[i][S]=0;
for(int T=0;T<(1<<K+1);T++){
int s=(K+1-__builtin_popcount(T)&1 ? mod-1 : 1);
for(int son:e[k])
if ((d[son])&&(d[son]<=K))s=(ll)s*sum[son][T]%mod;
h[0]=1;
for(int i=0;i<t[k];i++)h[1<<i]=sum[v[i]][T];
for(int S=0;S<(1<<t[k]);S++){
int S0=lowbit(S);
h[S]=(ll)h[S0]*h[S^S0]%mod;
}
pw[0]=1,pw[1]=__builtin_popcount(T);
for(int i=2;i<=l[k];i++)pw[i]=(ll)pw[i-1]*pw[1]%mod;
for(int S=0;S<(1<<t[k]);S++){
int s0=(ll)s*h[(1<<t[k])-1^S]%mod;
for(int x=0;x<=l[k];x++)
g[x][S]=(g[x][S]+(ll)s0*C[l[k]][x]%mod*pw[l[k]-x])%mod;
}
}
for(int son:v){
fs[son]=0;
for(int i=K+1;i<=d[k];i++)fs[son]=add(fs[son],f[son][i]);
}
for(int i=K+1;i<=d[k];i++){
pw[0]=1,pw[1]=n-i;
for(int i=2;i<=l[k];i++)pw[i]=(ll)pw[i-1]*pw[1]%mod;
for(int son:v)fs[son]=add(fs[son],mod-f[son][i]);
for(int x=0;x<=l[k];x++){
h[0]=1;
for(int i=0;i<t[k];i++)h[1<<i]=fs[v[i]];
for(int S=0;S<(1<<t[k]);S++){
int S0=lowbit(S);
h[S]=(ll)h[S0]*h[S^S0]%mod;
}
for(int S=0;S<(1<<t[k]);S++)
f[k][i]=(f[k][i]+(ll)pw[x]*g[x][S]%mod*h[S])%mod;
}
if (i==d[k])continue;
for(int x=0;x<=l[k];x++)
for(int S=0;S<(1<<t[k]);S++)g0[x][S]=g[x][S];
for(int x=0;x<=l[k];x++)
for(int y=0;y<x;y++)
for(int S=0;S<(1<<t[k]);S++)
g[y][S]=(g[y][S]+(ll)g[x][S]*C[x][y])%mod;
for(int j=0;j<t[k];j++)
for(int x=0;x<=l[k];x++)
for(int S=0;S<(1<<t[k]);S++)
if ((S>>j)&1){
int S0=(S^(1<<j));
g[x][S0]=(g[x][S0]+(ll)g[x][S]*f[v[j]][i])%mod;
}
for(int x=0;x<=l[k];x++)
for(int S=0;S<(1<<t[k]);S++)g[x][S]=add(g[x][S],mod-g0[x][S]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=0;i<=n;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
dfs(1,0);
for(int i=0;i<=n;i++)printf("%d\n",f[1][i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 15912kb
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: 1ms
memory: 24372kb
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: 1ms
memory: 11860kb
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: 9768kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 46664kb
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: 2ms
memory: 40564kb
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: 4ms
memory: 9868kb
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: 1ms
memory: 15956kb
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: -100
Wrong Answer
time: 2ms
memory: 32460kb
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 463557323 253920328 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 2nd numbers differ - expected: '780146137', found: '463557323'