QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617507 | #4811. Be Careful | Lehe | RE | 1ms | 7696kb | C++14 | 1.7kb | 2024-10-06 15:56:27 | 2024-10-06 15:56:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define sec second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define pb push_back
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n,ans[210],dp[210][210],deg[210],pd[210];
vector<int>g[210];
int c[1LL<<18],pc[1LL<<18];
void out(int u)
{
cout<<"u="<<u<<":";
for(int i=0;i<=n;i++)cout<<dp[u][i]<<" ";
cout<<endl;
}
void dfs(int u,int f)
{
for(auto v:g[u])
if(v!=f)
{
deg[u]++;
dfs(v,u);
}
if(!deg[u])for(int i=0;i<=n;i++)dp[u][i]=1;
else
{
int m=deg[u];
// memset(c,0,sizeof(c));
for(int i=(1LL<<m)-1;i>0;i--)c[i]=0;
c[0]=1;
for(auto v:g[u])
{
if(v==f)continue;
memset(pd,0,sizeof(pd));
for(int i=0;i<=n;i++)(pd[min(i,m)]+=dp[v][i])%=mod;
for(int i=(1LL<<m)-1;i>=0;i--)pc[i]=c[i],c[i]=0;
for(int i=(1LL<<m)-1;i>=0;i--)
for(int j=0;j<=m;j++)
(c[j==m?i:(i|(1LL<<j))]+=pc[i]*pd[j]%mod)%=mod;
// cout<<"!v="<<v<<endl;
// cout<<" --- "<<u<<" "<<m<<endl;
// for(int i=0;i<(1LL<<m);i++)cout<<" --- "<<i<<" "<<c[i]<<endl;
}
// cout<<" "<<u<<" "<<m<<endl;
// for(int i=0;i<(1LL<<m);i++)cout<<" "<<i<<" "<<c[i]<<endl;
for(int i=0;i<(1LL<<m);i++)
{
int mex;
for(int j=0;j<=m;j++)
if(!(i&(1LL<<j)))
{
mex=j;
break;
}
(dp[u][mex]+=c[i])%=mod;
}
}
// out(u);
}
signed main()
{
// freopen("mex.in","r",stdin);
// freopen("mex.out","w",stdout);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1,0);
for(int i=0;i<=n;i++)cout<<dp[1][i]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7660kb
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: 5744kb
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: 5692kb
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: 1ms
memory: 5756kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5716kb
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: 5636kb
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: 5676kb
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: 7696kb
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: 5772kb
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: 1ms
memory: 5628kb
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: 5768kb
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: 5708kb
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: 1ms
memory: 5724kb
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: 5668kb
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: 5704kb
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
Runtime Error
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...