题目链接：https://qoj.ac/contest/1499/problem/8180
题目大意：给定 $n$ 个点的点权，求 $n$ 个点的所有图的权值和，一个图的权值定义为：如果不连通，则为 $0$ ，联通则为所有边双的点权和的乘积。
做法
知道 Cayley 公式乱做。（但是我赛时不知道这个公式 QAQ ）
时间复杂度：$O(n^3)$ 。
解释一下代码：
$cn[i]$ 是 $i$ 个点的联通图的数量。
$dp[i][j]$ 表示有 $j$ 个点，恰好有 $i$ 个连通块的图的权值和（一个图的权值定义为每个连通块大小的乘积）
$bn[i]$ 表示 $i$ 个点的边双联通块数量。
$ff[i]$ 表示 $n$ 个点中，指定的 $i$ 个点各在一个边双，且联通，且恰有 $i$ 个边双的图的数量。
$ge[i]$ 表示从 $n$ 个点中选 $i$ 个点的点权乘积的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
const int N=4e2+5;
int n;LL a[N];
LL fc[N],nfc[N];
LL ksm(LL x,LL y){
LL ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;y>>=1;
}
return ans;
}
void init(){
fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=n;i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
for(int i=2;i<=n;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
}
LL C(int x,int y){return fc[x]*nfc[y]%mod*nfc[x-y]%mod;}
namespace Graph{
LL cn[N],dp[N][N],bn[N];
LL f[N][N],ff[N];
void init(){
cn[1]=1;
for(int i=1;i<=n;i++){
cn[i]=ksm(2,i*(i-1)/2);
for(int j=1;j<i;j++)cn[i]=(cn[i]-cn[j]*ksm(2,(i-j)*(i-j-1)/2)%mod*C(i-1,j-1)%mod+mod)%mod;
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int k=0;k<j;k++){
int cnt=j-k;
dp[i][j]=(dp[i][j]+dp[i-1][k]*cn[cnt]%mod*C(j-1,cnt-1)%mod*cnt)%mod;
}
}
}
for(int i=1;i<=n;i++){
bn[i]=cn[i];
for(int j=1;j<i;j++){
LL now=1;
for(int k=1;k<=i-j;k++){
now=now*j%mod;
bn[i]=(bn[i]-bn[j]*C(i-1,j-1)%mod*dp[k][i-j]%mod*now%mod+mod)%mod;
}
}
}
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int k=0;k<j;k++){
int cnt=j-k;
f[i][j]=(f[i][j]+f[i-1][k]*C(j-i,cnt-1)%mod*bn[cnt]%mod*cnt)%mod;
}
}
}
ff[1]=bn[n];for(int i=2;i<=n;i++)ff[i]=f[i][n]*ksm(n,i-2)%mod;
}
}
LL ge[N];
int main(){
scanf("%d",&n);
init();
Graph::init();
ge[0]=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
for(int j=i;j>=1;j--)ge[j]=(ge[j-1]*a[i]+ge[j])%mod;
}
LL ans=0;
for(int i=1;i<=n;i++){
ans=(ans+ge[i]*Graph::ff[i])%mod;
}
printf("%lld\n",ans);
return 0;
}
|
