神奇计数题。
先将所有确定的边连起来,一个比较关键的点是,将每个方案的贡献摊到每一个环上,即统计每个可能的环的方案数。设 \(a_i=-1\) 的数量为 \(num\)。
对于基环树来说,不论其他点怎么选这个环都存在,贡献为 \(n^{num}\)。
对于若干树构成的环来说,这种环有 $(t-1)!\prod \limits_{i=1}^t sz_i $ 个,对于每一个环,贡献为 \(n^{num-t}\)。
将树的贡献放到 dp 里面即可。
#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define fr first
#define se second
#define p 998244353
#define ll long long
#define pii pair<int,int>
ll ans,fac[N],mi[N],f[N][N];
int n,m,num,a[N],vis[N];
basic_string<int> G[N];
pii dfs(int u){
vis[u]=1;pii ans={1,G[u].size()};
for(int v:G[u])if(!vis[v]){
pii x=dfs(v);
ans.fr+=x.fr;ans.se+=x.se;
}return ans;
}
int main(){
scanf("%d",&n);
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
mi[0]=1;for(int i=1;i<=n;i++)mi[i]=mi[i-1]*n%p;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==-1)++num;
else G[i]+=a[i],G[a[i]]+=i;//printf("%d %d\n",a[i],i);
}
for(int i=1;i<=n;i++)if(!vis[i]){
pii x=dfs(i);
if(x.fr==x.se/2)ans+=mi[num]%p;
else a[++m]=x.fr;
}
f[0][0]=1;
for(int i=1;i<=m;i++){
f[i][0]=1;
for(int j=1;j<=m;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i])%p;
}
for(int i=1;i<=m;i++)
ans=(ans+f[m][i]*fac[i-1]%p*mi[m-i]%p)%p;
printf("%lld",ans);
}
标签:pii,fr,int,num,ans,ARC140D,define
From: https://www.cnblogs.com/xcyyyyyy/p/18336690