QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406620 | #4811. Be Careful | Bronya | RE | 6ms | 10244kb | C++14 | 3.1kb | 2024-05-07 15:19:03 | 2024-05-07 15:19:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int f[205][205],lim[205],suf[205][205];
int n;
struct edge{
int obj;
int last;
}e[405];
int head[205],g;
void link(int u,int v){
e[++g].obj=v;
e[g].last=head[u];
head[u]=g;
}
bool pd[205];
void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].last){
int v=e[i].obj;
if(v==fa)continue;
dfs(v,u);pd[u]=true;
}
}
const int B=15,mo=998244353;
int add(int u,int v){
return (u+v>=mo?u+v-mo:u+v);
}
int f2[1<<19],sav[1<<19];
int dp[1<<19][205],dp2[1<<19][205];
int pw[205][205];
int C[205][205];
void Solve(vector<int>son1,vector<int>son2,int hav,int x){
int ma=0;lim[x]=son1.size()+son2.size()+hav;
for(auto v:son1)ma=max(ma,lim[v]);
f2[0]=1;ma++;
for(auto v:son1){
for(int i=0;i<(1<<ma);i++){
for(int j=0;j<ma;j++)
sav[i|(1<<j)]=add(sav[i|(1<<j)],f2[i]*1ll*f[v][j]%mo);
}
for(int i=0;i<(1<<ma);i++)f2[i]=sav[i],sav[i]=0;
}
int m=son2.size();
for(int i=0;i<(1<<ma);i++){
if(!f2[i])continue;
for(int s=0;s<(1<<m);s++)
for(int k=0;k<=hav;k++)
dp[s][k]=dp2[s][k]=0;
dp[0][0]=1;
for(int j=0;j<=lim[x];j++){
if(j<ma&&(i&(1<<j))){
for(int s=0;s<(1<<m);s++)
for(int k=0;k<=hav;k++)
dp2[s][k]=dp[s][k],dp[s][k]=0;
}
for(int s=0;s<(1<<m);s++)
for(int k=0;k<=hav;k++){
int S=(((1<<m)-1)^s),mor=pw[n-j][hav-k];
if(!dp[s][k])continue;
while(S){
int l=__lg(S);
mor=1ll*mor*suf[son2[l]][j+1]%mo;
S^=(1<<l);
}
f[x][j]=add(f[x][j],1ll*mor*dp[s][k]%mo*1ll*f2[i]%mo);
}
for(int l=0;l<m;l++){
for(int s=0;s<(1<<m);s++){
if(s&(1<<l))continue;
for(int k=0;k<=hav;k++)
dp2[s|(1<<l)][k]=add(dp2[s|(1<<l)][k],1ll*add(dp[s][k],dp2[s][k])*f[son2[l]][j]%mo);
}
}
for(int s=0;s<(1<<m);s++)
for(int k=hav;k>=0;k--)
for(int l=0;l<k;l++){
dp2[s][k]=add(dp2[s][k],1ll*add(dp[s][l],dp2[s][l])*C[hav-l][k-l]%mo);
}
for(int s=0;s<(1<<m);s++)
for(int k=0;k<=hav;k++)
dp[s][k]=dp2[s][k],dp2[s][k]=0;
}
f2[i]=0;
}
}
bool cmp(int x,int y){
return lim[x]<lim[y];
}
void dfs2(int u,int fa){
vector<int>son;
int hav=0;
for(int i=head[u];i;i=e[i].last){
int v=e[i].obj;
if(v==fa)continue;
if(!pd[v])hav++;
else {
dfs2(v,u);
son.push_back(v);
}
}
sort(son.begin(),son.end(),cmp);
vector<int>son1,son2;
int mi=1e9,fj=0;
for(int i=0;i<son.size();i++){
int v=son[i];
if(lim[v]+son.size()-i-1<mi)
mi=lim[v]+son.size()-i-1,fj=i;
}
for(int i=0;i<son.size();i++)
if(i<=fj)son1.push_back(son[i]);
else son2.push_back(son[i]);
Solve(son1,son2,hav,u);
for(int i=n;i>=0;i--)suf[u][i]=add(suf[u][i+1],f[u][i]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
link(u,v);link(v,u);
}
for(int i=0;i<=n;i++){
pw[i][0]=1;
for(int j=1;j<=n;j++)pw[i][j]=1ll*pw[i][j-1]*i%mo;
}
C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=add(C[i-1][j-1],C[i-1][j]);
}
dfs(1,0);
dfs2(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: 7896kb
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: 9928kb
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: 8136kb
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: 8144kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7864kb
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: 1ms
memory: 9948kb
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: 1ms
memory: 9948kb
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: 7876kb
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: 1ms
memory: 9880kb
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: 0ms
memory: 9960kb
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: 1ms
memory: 9972kb
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: 1ms
memory: 8200kb
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: 0ms
memory: 7988kb
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: 1ms
memory: 7968kb
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: 0ms
memory: 7952kb
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: 0
Accepted
time: 6ms
memory: 10244kb
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:
211917199 369375874 201944418 582671162 183066248 639389350 952947539 137147613 216366713 398936459 73236543 354059031 727857197 121548413 610762100 573534011 706945631 286154195 226699593 267771858 823273748 233587424 176942776 226493975 707601105 339075191 694353149 944734662 932707579 934386415 4...
result:
ok 201 numbers
Test #17:
score: -100
Runtime Error
input:
200 2 199 95 2 2 75 177 2 66 2 157 2 85 2 2 193 2 26 8 2 38 2 151 2 2 56 63 2 2 138 2 59 190 2 2 36 2 120 156 2 115 2 2 118 171 2 6 2 113 2 20 2 83 2 2 176 33 2 153 2 2 169 22 2 2 159 2 27 87 2 2 129 2 44 174 2 2 93 77 2 2 122 2 125 2 23 2 81 112 2 173 2 2 51 32 2 96 2 184 2 116 2 67 2 2 94 2 104 19...