QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406550 | #4811. Be Careful | lexiyvv | RE | 0ms | 0kb | C++17 | 3.5kb | 2024-05-07 13:46:38 | 2024-05-07 13:46:38 |
answer
#include <bits/stdc++.h>
#define int long long
#define __int128 int
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];
#define LIM 23
int L[(1<<LIM)+5],r[(1<<LIM)+5],G0[(1<<LIM)+5],G2[(1<<LIM)+5],vis[(1<<LIM)+5];
unordered_map<int,int>mp;
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);
sort(v[x].begin(),v[x].end(),[&](int x,int y){return v[x].size()<v[y].size();});
int tmp=0;
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
int cnt=0;
for(int j=0;j<=n;j++){
if(dp[y][j]!=0)cnt=j+1;
}
tmp=max(tmp,cnt);
}
if(tmp<=LIM){
for(int i=0;i<(1<<tmp);i++)L[i]=0;
L[0]=1;
int tmp2=0;
int T=0,T2=0;
G0[++T]=0;
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
int cnt=0;
T2=0;
for(int I=1;I<=T;I++)vis[G0[I]]=0;
for(int j=0;j<n;j++){
if(dp[y][j]!=0){
cnt=j+1;
for(int I=1;I<=T;I++){
int i=G0[I];
if(!vis[i|(1<<j)])vis[i|(1<<j)]=1,G2[++T2]=(i|(1<<j));
(r[i|(1<<j)]+=L[i]*dp[y][j])%=mod;
}
}
}
for(int i=1;i<=T2;i++)
G0[i]=G2[i];
T=T2;
tmp2=max(tmp2,cnt);
for(int i=0;i<(1<<tmp2);i++)
L[i]=r[i],r[i]=0;
}
for(int I=1;I<=T;I++){
int i=G0[I];
vis[i]=0;
int a=i,w=L[i];
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++;
}
}
return ;
}
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
g.clear();
int cnt=0;
for(int j=0;j<=n;j++)
if(dp[y][j]!=0){
cnt++;
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(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
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;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
5 1 2 1 3 2 4 2 5