QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#764447 | #8049. Equal Sums | byron10000 | WA | 2ms | 10144kb | C++14 | 1.8kb | 2024-11-20 09:10:45 | 2024-11-20 09:10:46 |
Judging History
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'