给定 ,求满足以下条件的 个点的有向图 的个数:
- 是个竞赛图,即 没有重边和自环且对于所有 均满足 和 中只有一个满足;
- 只有 个 满足 且 ;
求所有满足条件的 中的强连通分量的个数和,对 取模。
,。
首先有一个结论:
个点的竞赛图 中的 SCC(strongly connected components)个数等价于:
把 划分为两个集合 和 (可以为空)使得 , 的方案数减一
证明:
考虑缩点,缩完点后的图显然还是竞赛图且是个 DAG,那么它的拓扑序唯一,设其为 ,那么显然 , 是合法的,这样划分一共有 种方案。
而其它划分方法显然不合法,得证。
考虑设 为加入了编号 的点,,从编号小的点连向编号大的点的边有 条的方案数,那么转移考虑新加入一个编号最大的点 :
答案即为 ,时间复杂度 。
代码如下:
// Problem: [ARC163D] Sum of SCC
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc163_d
// Memory Limit: 1 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
using namespace std;
const int S=1005,MS=35,p=998244353;
int n,m;
int C[S][S];
int f[MS][MS][S];
inline void add(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
int main()
{
C[0][0]=1;
for(int i=1;i<=S-3;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
scanf("%d%d",&n,&m);
f[0][0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n-i;j++)
{
for(int k=0;k<=m;k++)
{
for(int l=0;l<=i&&k+j+l<=m;l++) add(f[i+1][j][k+j+l],1ll*C[i][l]*f[i][j][k]%p);
for(int l=0;l<=j&&k+l<=m;l++) add(f[i][j+1][k+l],1ll*C[j][l]*f[i][j][k]%p);
}
}
}
int ans=0;
for(int i=0;i<=n;i++) add(ans,f[i][n-i][m]);
add(ans,p-C[n*(n-1)/2][m]);
printf("%d\n",ans);
return 0;
}