题解：AT_arc163_d [ARC163D] Sum of SCC

· · 个人记录

题目传送门

题意

给出 n 和 m，表示有一个 n 个点的竞赛图，要求从编号小的点向编号大的点的连边恰好 m 条，询问在所有满足条件的竞赛图中，强连通分量的个数之和。

分析

首先要知道什么事竞赛图，竞赛图简单来说就是有向完全图。竞赛图有很多重要的性质，我们在这题中需要用到其中一个，即竞赛图缩完点后呈链状。如下图所示。

图中标红的边，我称之为主边，蓝色的称之为副边，他们都是竞赛图缩完点后的边。

接下来，急需注意力。我们注意到对于每一条主边，我们如果把它断开，主边左边的点为集合 A，主边右边的点为集合 B。集合 A 中的点到集合 B 中的点的路径方向全部相同。基于这个性质我们就会发现，我们可以根据能划分出多少中集合 A 和集合 B 来计算强连通分量个数。不过集合 A 和集合 B 都可以为空，所以最终算出来的答案还要减去不同竞赛图的数量。

知道该怎么算后，我们考虑怎么具体实现。考虑 dp。我们定义 dp_{i,j,k} 表示集合 A 中有 i 个点，集合 B 中有 j 个点，从编号小连向编号大的点有 k 条。我们考虑如何转移，每新增一个点，分类讨论一下，如果放在集合 A 中，那么还要枚举集合 A 中有多少个点和它连边时是编号小连编号大。转移式就是，dp_{i+1,j,k+x}=dp_{i,j,k}\times C(i,x) 其中 C(i,x) 是组合数。同理，如果放在集合 B 中，转移式就是 dp_{i,j+1,k+x+i}=dp_{i,j,k}\times C(j,x)。为什么是 k+x+i 呢，因为集合 A 中所有点和新的点连边时都可以产生贡献，所以还要加上 i。

最终是同级答案，答案统计满足 i+j=n 并且 k=m 的 dp_{i,j,k} 的和即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const int N=50;
ll n,m,c[N*N][N*N],dp[N][N][N*N>>1],ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    ll len=n*(n-1)/2;
    c[0][0]=1;
    for(int i=1;i<=len;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            c[i][j]%=mod;
        }
    }
    dp[0][0][0]=1;
    for(int u=0;u<n;u++){
        for(int i=0,j=u;i<=u;i++,j--){
            for(int k=0;k<=m;k++){
                for(int x=0;k+x<=m;x++){
                    (dp[i+1][j][k+x]+=dp[i][j][k]*c[i][x]%mod)%=mod;
                    (dp[i][j+1][k+x+i]+=dp[i][j][k]*c[j][x]%mod)%=mod;
                }
            }
        }
    }
    for(int i=0;i<=n;i++) ans=(ans+dp[i][n-i][m])%mod;
    cout<<(ans-c[len][m]+mod)%mod;
    return 0;
}