QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406490 | #4811. Be Careful | by_chance | RE | 0ms | 0kb | C++14 | 2.2kb | 2024-05-07 12:54:44 | 2024-05-07 12:54:45 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=205,P=998244353;
int n,leaf[N],f[N][N],C[N][N],w[N][N],s[N][N];vector<int> G[N];
struct bit{
ll x,y;
int get(int id){if(id<=100)return (x>>id)&1;else return (y>>id-100)&1;}
void teg(int id){if(id<=100)x|=(((ll)1)<<id);else y|=(((ll)1)<<id-100);}
};
bool operator <(const bit&a,const bit&b){return a.x==b.x?a.y<b.y:a.x<b.x;}
map<bit,int> mp1,mp2;vector<int> dp1,dp2;
void dfs(int u,int fa){
if(fa&&G[u].size()==1){
for(int i=0;i<=n;i++)f[u][i]=1;
leaf[u]=1;return;
}
for(int v:G[u])if(v!=fa)dfs(v,u);
dp1={0,1};mp1[{0,0}]=1;int x=0;
sort(G[u].begin(),G[u].end(),[&](int x,int y){
return G[x].size()<G[y].size();
});
for(int v:G[u])if(v!=fa&&!leaf[v]){
int tot=0;
for(auto it:mp1){
auto st=it.first;int val=dp1[it.second];
for(int i=0;f[v][i];i++){
auto st2=st;st2.teg(i);
if(!mp2[st2])mp2[st2]=++tot,dp2.resize(tot+1);
int&c=dp2[mp2[st2]];c=(c+1ll*f[v][i]*val)%P;
}
}
mp1=mp2;dp1=dp2;mp2.clear();dp2.clear();
}else x+=leaf[v];
for(auto it:mp1){
auto st=it.first;int val=dp1[it.second],y=0;
for(int i=0;y<=x;i++)
if(st.get(i)==0)f[u][i]=(f[u][i]+1ll*val*s[x][y])%P,++y;
}mp1.clear();dp1.clear();
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
C[i][j]=(j?(C[i-1][j-1]+C[i-1][j])%P:1);
for(int i=1;i<=n;i++){
w[i][0]=1;
for(int j=1;j<=n;j++)
w[i][j]=1ll*w[i][j-1]*i%P;
}
for(int x=0;x<=n;x++)
for(int y=0;y<=n;y++)
for(int z=0;z<=y;z++){
int val=1ll*C[y][z]*w[n-z][x]%P;
if(z&1)s[x][y]=(s[x][y]-val+P)%P;
else s[x][y]=(s[x][y]+val)%P;
}
dfs(1,0);
for(int i=0;i<=n;i++)cout<<f[1][i]<<endl;
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
5 1 2 1 3 2 4 2 5