QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783245#9566. TopologyDarwin_ArnoldCompile Error//C++202.1kb2024-11-26 02:59:042024-11-26 02:59:04

Judging History

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

  • [2024-11-26 02:59:04]
  • 评测
  • [2024-11-26 02:59:04]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010;
ll mod=998244353;
int n;
vector<int>G[N];
ll L[N];
int sz[N];
int p[N];
ll f[N];
ll g[N][N];
ll dp[N][N];
ll S[N][N];
ll ans[N];
ll fast_pow(ll a,ll m)
{
    ll base=a;
    ll res=1;
    while(m)
    {
        if(m&1)res=(int)((res*1ll*base)%mod);
        base=((base*1ll*base)%mod;
        m>>=1;
    }
    return res;
}
ll mod_inverse(ll x)
{
    return (ll)(fast_pow(x,mod-2));
}
ll C(ll x,ll y)
{
    return (ll)((((L[x]*1ll*mod_inverse(L[y]))%mod)*1ll*mod_inverse(L[x-y]))%mod);
}
void dfs_1(int u,int fa)
{
    int temp=L[sz[u]-1];
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        dfs_1(v,u);
        temp=(ll)((temp*1ll*f[v])%mod);
        temp=(ll)((temp*1ll*mod_inverse(L[sz[v]]))%mod);
        //printf("%d\n",temp);
    }
    f[u]=temp;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        g[u][v]=(ll)((((f[u]*1ll*mod_inverse(f[v]))%mod)*mod_inverse(C(sz[u]-1,sz[v])))%mod);
    }
}
void dfs_2(int u,int fa)
{
    if(u!=1)
    {
        for(int i=1;i<=n;i++)
        {
            S[fa][i]=(ll)(((S[fa][i-1]*1ll+(dp[fa][i]*1ll*C(n-sz[u]-i,sz[fa]-sz[u]-1))%mod))%mod);
            dp[u][i]=(ll)(g[fa][u]*1ll*S[fa][i-1])%mod;
        }
    }
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        dfs_2(v,u);
    }
}
int main()
{
    scanf("%lld",&n);
    L[0]=1;
    for(int i=1;i<=n;i++)L[i]=(int)((i*1ll*L[i-1])%mod);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%lld",&x);
        p[i]=x;
        G[x].push_back(i);
    }
    for(int i=1;i<=n;i++)sz[i]=1;
    for(int i=n;i>=2;i--)sz[p[i]]+=sz[i];
    dp[1][1]=1;
    dfs_1(1,0);
    dfs_2(1,0);
    for(int i=1;i<=n;i++)
    {
        ans[i]=(ll)((((dp[i][i]*1ll*f[i])%mod)*1ll*C(n-i,sz[i]-1))%mod);
    }
    /*
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",g[i][j]);
        }
        printf("\n");
    }
    */
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",ans[i]);
    }
    return 0;
}

Details

answer.code: In function ‘long long int fast_pow(long long int, long long int)’:
answer.code:23:34: error: expected ‘)’ before ‘;’ token
   23 |         base=((base*1ll*base)%mod;
      |              ~                   ^
      |                                  )
answer.code: In function ‘int main()’:
answer.code:72:15: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
   72 |     scanf("%lld",&n);
      |            ~~~^  ~~
      |               |  |
      |               |  int*
      |               long long int*
      |            %d
answer.code:78:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
   78 |         scanf("%lld",&x);
      |                ~~~^  ~~
      |                   |  |
      |                   |  int*
      |                   long long int*
      |                %d
answer.code:72:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
answer.code:78:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |         scanf("%lld",&x);
      |         ~~~~~^~~~~~~~~~~