专栏文章

题解：AT_arc163_d [ARC163D] Sum of SCC

hhoko
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9in5g
此快照首次捕获于
2025/12/02 15:34
3 个月前
此快照最后确认于
2025/12/02 15:34
3 个月前
查看原文

题目传送门

题意

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

分析

首先要知道什么事竞赛图，竞赛图简单来说就是有向完全图。竞赛图有很多重要的性质，我们在这题中需要用到其中一个，即竞赛图缩完点后呈链状。如下图所示。
图中标红的边，我称之为主边，蓝色的称之为副边，他们都是竞赛图缩完点后的边。
接下来，急需注意力。我们注意到对于每一条主边，我们如果把它断开，主边左边的点为集合 AA，主边右边的点为集合 BB。集合 AA 中的点到集合 BB 中的点的路径方向全部相同。基于这个性质我们就会发现，我们可以根据能划分出多少中集合 AA 和集合 BB 来计算强连通分量个数。不过集合 AA 和集合 BB 都可以为空，所以最终算出来的答案还要减去不同竞赛图的数量。
知道该怎么算后，我们考虑怎么具体实现。考虑 dpdp。我们定义 dpi,j,kdp_{i,j,k} 表示集合 AA 中有 ii 个点，集合 BB 中有 jj 个点，从编号小连向编号大的点有 kk 条。我们考虑如何转移，每新增一个点，分类讨论一下，如果放在集合 AA 中，那么还要枚举集合 AA 中有多少个点和它连边时是编号小连编号大。转移式就是，dpi+1,j,k+x=dpi,j,k×C(i,x)dp_{i+1,j,k+x}=dp_{i,j,k}\times C(i,x) 其中 C(i,x)C(i,x) 是组合数。同理，如果放在集合 BB 中，转移式就是 dpi,j+1,k+x+i=dpi,j,k×C(j,x)dp_{i,j+1,k+x+i}=dp_{i,j,k}\times C(j,x)。为什么是 k+x+ik+x+i 呢，因为集合 AA 中所有点和新的点连边时都可以产生贡献，所以还要加上 ii。
最终是同级答案，答案统计满足 i+j=ni+j=n 并且 k=mk=m 的 dpi,j,kdp_{i,j,k} 的和即可。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...