QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#406490#4811. Be Carefulby_chanceRE 0ms0kbC++142.2kb2024-05-07 12:54:442024-05-07 12:54:45

Judging History

你现在查看的是最新测评结果

  • [2024-05-07 12:54:45]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-07 12:54:44]
  • 提交

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

output:


result: