QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629884#5139. DFS Order 2999#Compile Error//C++142.2kb2024-10-11 15:21:192024-10-11 15:21:19

Judging History

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

  • [2024-10-11 15:21:19]
  • 评测
  • [2024-10-11 15:21:19]
  • 提交

answer

#include<iostream>
#include<vector>
using namespace std;
#define M 505
#define P 998244353
vector<int>d[M];
int dp[M][M],dpf[M][M],sz[M],w[M],ls[M][M],now[M][M],fc[M];
void dfs(int x,int f){
    w[x]=1;sz[x]=1;
    for(int i=0;i<(int)d[x].size();++i){
        int v=d[x][i];
        if(v==f)continue;
        dfs(v,x);
        w[x]=1ll*w[x]*w[v]%P;
        sz[x]+=sz[v];
    }
    int tot1=0,tot2=0,ac=1;
    memset(ls,0,sizeof(ls));
    ls[0][0]=1;
    for(int i=0;i<(int)d[x].size();++i){
        int v=d[x][i];
        if(v==f)continue;
        for(int j=tot1;j>=0;--j)
            for(int k=0;k<=tot2;++k)
                ls[j+1][k+sz[v]]=(ls[j+1][k+sz[v]]+1ll*ls[j][k])%P;
        ac=1ll*ac*w[v]%P;
        tot1++;
        tot2+=sz[v];
    }w[x]=1ll*w[x]*fc[tot1]%P;
    for(int i=0;i<(int)d[x].size();++i){
        int v=d[x][i];
        if(v==f)continue;
        for(int j=0;j<=tot1;++j)for(int k=0;k<=tot2;++k)now[j][k]=ls[j][k];
        for(int j=0;j<tot1;++j){
            for(int k=0;k+sz[v]<=tot2;++k)
                now[j+1][k+sz[v]]=(now[j+1][k+sz[v]]-now[j][k])%P;
        }
        for(int j=0;j<=tot1;++j)
            for(int k=0;k<=tot2;++k){
                dpf[v][k+1]=(dpf[v][k+1]+1ll*fc[j]*fc[tot1-j-1]%P*now[j][k]%P*ac)%P;
            }
    }
}
int pw(int x,int p){
    int ans=1;
    while(p){
        if(p&1)ans=1ll*ans*x%P;
        x=1ll*x*x%P;p>>=1;
    }
    return ans;
}
void Dfs(int x,int f){
    if(x==1){
        for(int i=1;i<=sz[1];++i)dp[1][i]=0;
        dp[1][1]=w[1];
    }
    else{
        int t=pw(w[f],P-2);
        for(int i=1;i<=sz[1];++i)
            for(int j=1;i+j<=sz[1];++j){
                dp[x][i+j]=(dp[x][i+j]+1ll*dp[f][i]*t%P*dpf[x][j])%P;
            }
    }
    for(int i=0;i<(int)d[x].size();++i){
        int v=d[x][i];
        if(v==f)continue;
        Dfs(v,x); 
    }
}
int main(){
    fc[0]=fc[1]=1;
    for(int i=2;i<M;++i)fc[i]=1ll*i*fc[i-1]%P;
    int n;
    scanf("%d",&n);
    for(int i=1,x,y;i<n;++i){
        scanf("%d%d",&x,&y);
        d[x].push_back(y);
        d[y].push_back(x);
    }
    dfs(1,0);
    Dfs(1,0);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            printf("%d ",(dp[i][j]+P)%P);
        puts("");
    }
}

详细

answer.code: In function ‘void dfs(int, int)’:
answer.code:18:5: error: ‘memset’ was not declared in this scope
   18 |     memset(ls,0,sizeof(ls));
      |     ^~~~~~
answer.code:3:1: note: ‘memset’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
    2 | #include<vector>
  +++ |+#include <cstring>
    3 | using namespace std;
answer.code: In function ‘int main()’:
answer.code:74:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
answer.code:76:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   76 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~