LOJ6094 「Codeforces Round #418」归乡迷途 做题记录

给定长 $n$ 的序列 $d$，求有多少个 $n$ 个点的有标号简单无向图（无自环重边）满足：

• 点 $i$ 的度数为 $d_i$；
• 点 $1$ 到点 $i$ 有且仅有一条最短路；
• $\forall j<i$，点 $1$ 到点 $i$ 的最短路长度大于等于点 $1$ 到点 $j$ 的；

对 $998244353$ 取模。

$3\le n\le 300$，$2\le d_i\le 3$。

考虑 bfs，显然图可以分成若干层，每一层点的编号连续且 bfs 树上的横叉边都在同一层内。

那么不难想到设 $f_{i,j}$ 表示处理完前 $i$ 个点，最后一层往下连了 $j$ 条边的方案数。

转移时下一层的区间一定是 $[i+1,i+j-1]$，且区间内去掉当前层的 $j$ 条边就只剩下一度点和二度点。那么不难想到设 $g_{i,j,k}$ 表示一层内有 $i$ 个 $1$ 度点和 $j$ 个二度点，往下一层连了 $k$ 条边的内部连边方案数。则有：

$f_{i,j}\times g_{c1,c2,k}\times j!\to f_{i+j,k}$

其中 $c1$ 和 $c2$ 表示 $d_{[i+1,i+j-1]}$ 中 $2$ 和 $3$ 的个数。

但是发现这样会算重，因为二度点无论连哪边都是一样的。

所以若上一层有 $l$ 个二度点是两边都往下连的，则转移时需要除掉 $2^l$。

这个问题是好处理的，只需要把 $2^l$ 放进 $g$ 中即可。

现在来考虑 $g$ 怎么求，首先显然有 $g_{0,0,0}=1$。

不难发现一度点和二度点之间的顺序是没有关系的，所以不妨钦定先放一度点再放二度点。

下文 x 表示一度点，o 表示二度点，- 表示层内连边，+ 表示向下一层的连边

对于没有二度点的情况，考虑最后一个一度点 $u$：

• u+ 型：$g_{i-1,0,k-1}$；
• x-u 型：$g_{i-2,0,k}\times (i-1)$；

对于有二度点的情况，考虑最后一个二度点 $u$。为了避免算重，$u$ 多出来的边直接往下连：

• +u+ 型：$g_{i,j-1,k-2}\times \frac{1}{2}$，其中 $\frac{1}{2}$ 是转移时的 $2^l$；
• x-u+ 型：$g_{i-1,j-1,k-1}\times i$；
• -o-u+ 型：连出去的二度点规约为一个一度点，$g_{i+1,j-2,k-1}\times(j-1)$；
• x-u-x 型：$g_{i-2,j-1,k}\times \frac{i\times(i-1)}{2}$；
• x-u-o- 型：连出去的二度点规约为一个一度点，$g_{i,j-2,k}\times i\times (j-1)$；
• -o-u-o- 型：两个二度点都规约为一度点，$g_{i+2,j-3,k}\times \frac{(j-1)\times(j-2)}{2}$；

时间复杂度 $O(n^3)$，空间复杂度 $O(n^3)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=305,p=1000000007,inv2=(p+1)/2;

int fra[S];
int n,a[S];
int g[S][S][S],f[S][S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	g[0][0][0]=1;
	for(int k=0;k<=n;k++)
	{
		for(int j=0;j<=n&&j+k<=n;j++)
		{
			for(int i=0;i<=n&&i+j+k<=n;i++)
			{
				if(i+j*2<k) continue;
				if(i+j+k==0) continue;
				int &u=g[i][j][k];
				if(j==0)
				{
					// u-
					if(k>=1) add(u,g[i-1][j][k-1]);
					// u-x
					if(i>=2) add(u,1ll*g[i-2][j][k]*(i-1)%p);
				}
				else
				{
					// x-u-x
					if(i>=2) add(u,1ll*g[i-2][j-1][k]*i%p*(i-1)%p*inv2%p);
					// x-u-o- OR -o-u-x
					if(i>=1&&j>=2) add(u,1ll*g[i][j-2][k]*i%p*(j-1)%p);
					// -o-u-o-
					if(j>=3) add(u,1ll*g[i+2][j-3][k]*(j-1)%p*(j-2)%p*inv2%p);
					if(k>=1)
					{
						// x-u- OR -u-x
						if(i>=1) add(u,1ll*g[i-1][j-1][k-1]*i%p);
						// -o-u- OR -u-o-
						if(j>=2) add(u,1ll*g[i+1][j-2][k-1]*(j-1)%p);
						if(k>=2)
						{
							// -u-
							add(u,1ll*g[i][j-1][k-2]*inv2%p);
						}
					}
				}
			}
		}
	}
	f[1][a[1]]=qpow(fra[a[1]],p-2);
	for(int i=1;i<=n-1;i++)
	{
		int c1=0,c2=0;
		for(int j=i+1;j<=n;j++)
		{
			c1+=a[j]==2;
			c2+=a[j]==3;
			for(int k=0;k<=n&&k<=c1+c2*2;k++)
			{
				int pre=1ll*f[i][j-i]*g[c1][c2][k]%p*fra[j-i]%p;
				add(f[j][k],pre);
			}
		}
	}
	printf("%d\n",f[n][0]);
	return 0;
}