QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#406483 | #4811. Be Careful | alpha1022 | WA | 0ms | 3808kb | C++14 | 2.3kb | 2024-05-07 12:50:48 | 2024-05-07 12:50:50 |
Judging History
answer
//#pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,p1,p2,dp[205][205],lf[205];
int qpow[205][205],f[205],g[205],C[205][205],q[205][205];
__int128 fm2[205];
vector<int>v[205];
#define R 1
int F[205][(1<<R)+5],G[205][(1<<R)+5],t[205];
unordered_map<int,int>mp;
//const int mod2=1000000000000009;
void dfs(int x,int l){
int tg=0,cnt2=0;
for(auto y:v[x])
if(y!=l)dfs(y,x),tg=1,cnt2++;
if(!tg){
lf[x]=1;
return ;
}
vector<pair<__int128,int> >f,g;
f.push_back({0,1});
int cnt=0;
int lim=cnt2+1;
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
cnt++;
continue;
}
}
lim=min(lim,(int)(sqrt((n-cnt)*2)+0.1)+cnt);
// if(x==1)return ;
// if(n>150)lim=min(lim,27ll);
sort(v[x].begin(),v[x].end(),[&](int x,int y){return v[x].size()<v[y].size();});
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
g.clear();
for(int j=0;j<=n/2+1;j++)
if(dp[y][j]!=0)
for(auto i:f)
g.push_back({i.first|fm2[min(j,lim)],i.second*dp[y][j]%mod});
for(auto i:g)(mp[i.first]+=i.second)%=mod;
f.clear();
for(auto i:g){
int r=mp[i.first];
if(r)f.push_back({i.first,r}),mp[i.first]=0;
}
}
for(auto i:f){
int a=i.first,w=i.second;
int c=0;
for(int j=0;j<=n;j++){
if(!(a&fm2[j]))
(dp[x][j]+=w*q[j-c][cnt])%=mod;
else c++;
}
}
}
int p[205];
signed main(){
cin>>n;
fm2[0]=1;
for(int i=1;i<=n/2+1;i++)fm2[i]=fm2[i-1]*2;
f[0]=1;
for(int i=0;i<=n;i++){
int mul=1;
for(int j=0;j<=n;j++){
qpow[i][j]=mul;
(mul*=i)%=mod;
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i)C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
for(int j=0;j<=n;j++){
for(int k=0;j+k<=n;k++)
(q[0][j+k]+=f[j]*qpow[n][k]%mod*C[j+k][k])%=mod;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=1;j+k<=n;k++)
(g[j+k]+=f[j]*C[j+k][k])%=mod;
}
memcpy(f,g,sizeof(f));memset(g,0,sizeof(g));
for(int j=0;j<=n;j++){
for(int k=0;j+k<=n;k++)
(q[i+1][j+k]+=f[j]*qpow[n-i-1][k]%mod*C[j+k][k])%=mod;
}
}
for(int i=1;i<n;i++){
cin>>p1>>p2;
v[p1].push_back(p2);
v[p2].push_back(p1);
}
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: 0ms
memory: 3808kb
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: 0ms
memory: 3544kb
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: 0ms
memory: 3620kb
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: 3684kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3740kb
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: -100
Wrong Answer
time: 0ms
memory: 3680kb
input:
10 2 8 2 9 6 2 2 1 2 4 2 10 2 5 7 2 3 2
output:
114056481 100000000 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '114358881', found: '114056481'