QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764447#8049. Equal Sumsbyron10000WA 2ms10144kbC++141.8kb2024-11-20 09:10:452024-11-20 09:10:46

Judging History

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

  • [2024-11-20 09:10:46]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10144kb
  • [2024-11-20 09:10:45]
  • 提交

answer

#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
typedef __int128 i128;
const int MAXN=1e5+10; const long MOD=998244353;
void addto(long& x,long y){ x=(x+y)%MOD; }
int n; vector<int> G[MAXN];
long fac[MAXN],inv[MAXN];
int siz[MAXN];
vector<long> F[MAXN];
void merge(vector<long>& x,const vector<long>& y,int a,int b){
    auto z=x;
    RNG(i,0,int(x.size())-1){
        x[i]=0;
        RNG(j,max(0,i-int(y.size())+1),i) addto(x[i],z[j]*y[i-j]%MOD*(fac[a+b+i]*inv[a+j]%MOD*inv[b+i-j]%MOD)%MOD);
    }
}
void dfs(int u,int d){
    vector<long> f(d+1,1);
    for(int v:G[u]){
        dfs(v,d+1);
        merge(f,F[v],siz[u],siz[v]);
        siz[u]+=siz[v];
    }
    siz[u]++;
    F[u]=vector<long>(f.begin()+1,f.end());
}
long qpow(long x,int p){
    long ret=1;
    for(; p; p>>=1,x=x*x%MOD){
        if(p&1) ret=ret*x%MOD;
    }
    return ret;
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("0.in","r",stdin);
//  freopen("0.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    fac[0]=1; RNG(i,1,n) fac[i]=fac[i-1]*i%MOD;
    inv[n]=qpow(fac[n],MOD-2); IRNG(i,n-1,0) inv[i]=inv[i+1]*(i+1)%MOD;
    RNG(u,2,n,fa) cin>>fa,G[fa].push_back(u);
    dfs(1,1);
    cout<<F[1][0]<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 10144kb

input:

2 3
1 2
2 3
1 4
2 2
1 3

output:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'