[ABC389G] Odd Even Graph

发表于 分类于 ， 阅读次数：
赛时访问负数下标调半天。

Statement

给定偶数 \(n\)，对于 \(i=n-1,n,\ldots,\frac{n(n-1)}2\) 解决以下问题：

求满足以下条件的 \(n\) 点 \(i\) 边无向连通简单图数量：

  • 到 \(1\) 的最短路为奇数的结点个数等于到 \(1\) 的最短路为偶数的结点个数。

Data range：\(n\le 30\)，5s。

Solution

考虑按最短路一层层 dp。看看需要记什么：

  • 当前层的最短路 \(i\)；
  • 目前为止扩展到的点数 \(j\)；
  • 当前偶奇最短路数量之差 \(k\)；
  • 当前层结点个数 \(l\)（转移时要用）；
  • 目前为止连的边数 \(m\)。

那么就得到了 \(dp_{i,j,k,l,m}\) 的状态。

显然初值为 \(dp_{0,1,1,1,0}=1\)，答案为 \(dp_{*,n,0,*,i}\)；考虑从 \(dp_{i,j,k,l,m}\) 转移。

枚举下一层的点数 \(o\) 和新连的边数 \(p\)，则转移到 \(dp_{i+1,j+o,k+(-1)^{i+1}\cdot o,o,m+p}\)。考虑转移系数：

  • 有 \(\binom{n-j}o\) 种方法选择这 \(o\) 个点；
  • 显然第 \(i-1\) 层以前不可能向新层连边；那么相当于第 \(i\) 层的第 \(l\) 个点和新层的 \(o\) 个点加上新层内部连的边一共连 \(p\) 条的方案数，记为 \(f_{l,o,p}\)。

那么转移系数就是 \(\binom{n-j}o\cdot f_{l,o,p}\)。

下面计算 \(f\) 值，考虑 \(f_{x,y,z}\)。

枚举新层内部的边数（显然这里没有任何限制），那么设 \(g_{x,y,z}\) 为 \(i,i+1\) 层各有 \(x,y\) 个点时，之间连 \(z\) 条边的方案数，则有

\[f_{x,y,z}=\sum_{i=0}^{y(y-1)/2}\binom{y(y-1)/2}ig_{x,y,z-i}\]

（此处 \(i\) 仅为循环变量，与状态里的 \(i\) 无关）

但是注意，不同层连边有限制——如果 \(i+1\) 层一个点一条边也没往外连，那么它的最短路就 \(>i+1\) 了。所以容斥，枚举一条边也没连的点：

\[g_{x,y,z}=\sum_{i=0}^y(-1)^i\binom yi\binom{x(y-i)}z\]

于是就 dp 完了。

算下时间复杂度：\(f\) 和 \(g\) 还有组合数的预处理显然可以忽略掉。转移时，可以发现 \(i,j,k,l,o\) 都是 \(O(n)\)，\(m\) 和 \(p\) 是 \(O(n^2)\)，所以总复杂度为 \(O(n^9)\)。

这东西一看就带着一个几百分之一的常数，写的精细一点就过了。

Code

（3.11s/87mb）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// Author: YE Minghan
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=31;
int n,MOD;
int dp[2][N][N<<1][N][N*N>>1];
int C[N*N>>1][N*N>>1],f[N][N][N*N>>1],g[N][N][N*N>>2];

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n>>MOD;
	for(int i=0;i<=n*n>>1;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
	}
	for(int x=0;x<n;x++)
		for(int y=0;y<=n-x;y++)
			for(int z=y;z<=x*y;z++)
				for(int i=0;i<=y&&(y-i)*x>=z;i++)
				{
					int t=1ll*C[y][i]*C[(y-i)*x][z]%MOD;
					g[x][y][z]=(g[x][y][z]+(i&1?MOD-t:t))%MOD;
				}
	for(int x=0;x<n;x++)
		for(int y=0;y<=n-x;y++)
			for(int z=y,t=y*(y-1)>>1;z<=x*y+t;z++)
				for(int i=max(0,z-x*y);i<=min(t,z);i++)
					f[x][y][z]=(f[x][y][z]+1ll*C[t][i]*g[x][y][z-i])%MOD;
	dp[1][1][N+1][1][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
			for(int k=N-j;k<=N+j;k++)
				for(int l=0;l<=j-i;l++)
					for(int m=j-1;m<=j*(j-1)>>1;m++)
						dp[0][j][k][l][m]=dp[1][j][k][l][m],dp[1][j][k][l][m]=0;
		for(int j=i+1;j<=n;j++)
			for(int k=N-j;k<=N+j;k++)
				for(int l=0;l<=j-i;l++)
					for(int m=j-1;m<=j*(j-1)>>1;m++)
					{
						int cr=dp[0][j][k][l][m];
						if(!cr)continue;
						for(int o=0;o<=n-j;o++)
							for(int p=o;p<=l*o+(o*(o-1)>>1);p++)
							{
								int &nxt=dp[1][j+o][k+(i&1?o:-o)][o][m+p];
								nxt=(nxt+1ll*C[n-j][o]*f[l][o][p]%MOD*cr)%MOD;
							}
					}
	}
	for(int i=n-1;i<=n*(n-1)>>1;i++)
		cout<<dp[1][n][N][0][i]<<" ";
	cout<<endl;

	return 0;
}