ARC163D Sum of SCC 做题记录

给定 n,mn,m,求满足以下条件的 nn 个点的有向图 GG 的个数:

  • GG 是个竞赛图,即 GG 没有重边和自环且对于所有 1i<jn1\le i<j\le n 均满足 (ij)G(i\to j)\in G(ji)G(j\to i)\in G 中只有一个满足;
  • 只有 mm(i,j)(i,j) 满足 1i<jn1\le i<j\le n(ij)G(i\to j)\in G
    求所有满足条件的 GG 中的强连通分量的个数和,对 998244353998244353 取模。
    1n301\le n\le 301mn(n1)21\le m\le \frac{n(n-1)}{2}

首先有一个结论:

nn 个点的竞赛图 GG 中的 SCC(strongly connected components)个数等价于:

{1,2,3,,n}\{1,2,3,\dots,n\} 划分为两个集合 AABB(可以为空)使得 uA,vB\forall u\in A,v\in B(ij)G(i\to j)\in G 的方案数减一

证明:

考虑缩点,缩完点后的图显然还是竞赛图且是个 DAG,那么它的拓扑序唯一,设其为 {scc1,scc2,scc3,,sccsz}\{scc_1,scc_2,scc_3,\dots,scc_{sz}\},那么显然 0isz\forall 0\le i\le szA={scc1,scc2,,scci},B={scci+1,scci+2,,sccsz}A=\{scc_1,scc_2,\dots,scc_i\},B=\{scc_{i+1},scc_{i+2},\dots,scc_{sz}\} 是合法的,这样划分一共有 sz+1sz+1 种方案。

而其它划分方法显然不合法,得证。

考虑设 fi,j,kf_{i,j,k} 为加入了编号 [1,i+j][1,i+j] 的点,A=i,B=j|A|=i,|B|=j,从编号小的点连向编号大的点的边有 kk 条的方案数,那么转移考虑新加入一个编号最大的点 i+j+1i+j+1

{(il)fi,j,kfi+1,j,k+j+l(jl)fi,j,kfi,j+1,k+l\begin{cases} \binom{i}{l}f_{i,j,k}\to f_{i+1,j,k+j+l}\\ \binom{j}{l}f_{i,j,k}\to f_{i,j+1,k+l} \end{cases}

答案即为 i+j=nfi,j,m(n(n1)2m)\sum\limits_{i+j=n}f_{i,j,m}-\binom{\frac{n(n-1)}{2}}{m},时间复杂度 O(n3m)O(n^3m)

代码如下:

// 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;
}