QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782678#9566. TopologyLudovicaCompile Error//C++141.5kb2024-11-25 20:58:592024-11-25 20:59:04

Judging History

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

  • [2024-11-25 20:59:04]
  • 评测
  • [2024-11-25 20:58:59]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=5010,M=4e5+10;
const int INF=1e18;
const int mod=998244353;
int n,fac[N],invfac[N],siz[N],mul[N],f[N],dp[N][N];
vector<int> adj[N];
int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
void init(){
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	invfac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%mod;
}
int C(int n,int m){
	if(n<m)return 0;
	return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
void dfs(int u){
	siz[u]=f[u]=mul[u]=1;
	for(auto v:adj[u]){
		dfs(v);
		siz[u]+=siz[v];
		mul[u]=mul[u]*mul[v]%mod;
	}
	mul[u]=mul[u]*siz[u]%mod;
	f[u]=fac[siz[u]]*qpow(mul[u],mod-2)%mod;
}
void dfs1(int u){
	for(auto v:adj[u]){
		int tmp=f[u]*mul[v]%mod*siz[u]%mod*qpow(siz[u]-siz[v],mod-2)%mod*invfac[siz[u]]%mod*fac[siz[u]-siz[v]]%mod;
		for(int i=1;i<=n;i++){
			dp[v][i]=dp[u][i-1]*tmp%mod*C(n-i+1-siz[v],siz[u]-siz[v]-1)%mod;
			dp[v][i]+=dp[v][i-1];
			dp[v][i]%=mod;
		}
		dfs1(v);
	}
}
void solve(){
	cin>>n;
	init();
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		adj[x].push_back(i);
	}
	dp[1][1]=1;
	dfs(1);
	dfs1(1);
	for(int i=1;i<=n;i++){
		dp[i][i]=dp[i][i]*f[i]%mod*C(n-i,siz[i]-1)%mod;
		cout<<dp[i][i]<<" \n"[i==n];
	}
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
     cin>>T;
    while(T--)solve();
    return 0;
}

Details

answer.code: In function ‘int main()’:
answer.code:67:11: error: ‘T’ was not declared in this scope
   67 |      cin>>T;
      |           ^