闲话

今日推歌：玛德琳娜电塔 - by 纯白 p feat. 洛天依 / warma
虽然曲子是活泼积极的感觉，但内核却是深深的悲剧与无助
感觉很多歌曲都会采用这种做法呢，比如说阿良良老师的《春风来》。

我等春风吹过来 梨花朵朵盛开
水暖春江 笑满园

对未来的美好幻想很多时候隐含着对可见未来和现实的哀叹。
这么一想 感觉《边城》的结局又多了些悲剧色彩。
《春风来》真的很好听。

说句题外话，阿良良老师的专辑《奇爱人生》的英文名是 Love Elegia，这里 Elegia 取哀歌义。

奇怪题

考虑一张 \(n\) 个点的无向图 \(G\) 以及它的邻接矩阵 \(g\)，如果 \(i,j\) 之间有边那么 \(g_{i,j}=1\)，否则 \(g_{i,j}=0\)。

下面是一个正常的 Floyd 算法:

void Floyd(int n) {
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j)
					g[i][j] |= g[i][k] && g[k][j];
}

下面是一个带参数 \(m\) 的 Super Brilliant 的 Floyd 算法：

void sbFloyd(int n,int m) {
	for (int k = 1; k <= n - m; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j)
					g[i][j] |= g[i][k] && g[k][j];
}

给定 \(n, m\)，计数有多少张有标号的 \(n\) 个点的图满足邻接矩阵扔进上面两种 Floyd 算法后得到的结果相同。

我们令 \(1\sim n - m\) 的点是黑点，剩下的点是白点。
这样我们可以描述题设为：图的任意连通块内两个点都可以找到一条除端点外只包含黑点的路径。

观察可以发现，只有白点的连通块必定是团；有黑点的连通块对应黑点的导出子图必定联通，每个白点都必定和一个黑点联通。
我们记 \(f(n, m)\) 为 \(n\) 个黑点 \(m\) 个白点的图的方案数，大小为 \(i\) 的简单无向联通图的方案数是 \(g(n)\)，则可以通过强制标号和讨论连通块种类（只有白点/有黑点）的方式得到转移：

\[\begin{aligned} f(n, m) =& \sum_{i = 1}^m f(n - i, m - i) \binom{m - 1}{i - 1} + \\ &
\sum_{i = 1}^{n - m} \sum_{j = 1}^m f(n - i - j, m - j) \binom{n - m}{i} \binom{m - 1}{j - 1} g(i)(2^i - 1)^j2^{j(j - 1) / 2}\end{aligned}\]

时间复杂度 \(O(n^4)\)。

这就是极限了吗？生成函数告诉你，不是的。

我们下面首先讨论一个大小的连通块的方案。只有白点的连通块对一个大小只有一种方案，不是重点。

对于黑点，我们需要分别描述各部分。假设大小为 \(i\) 的简单无向联通图的方案数是 \(f_i\)，这可以通过有标号 \(\text{Set}\) 的逆得到。
我们假设有 \(i\) 个黑点，\(j\) 个白点，则联通的方案是 \(f_i\)，每个白点向黑点连边的方案是 \((2^i - 1)^j\)，白点间互相联通的方案是 \(2^{j(j - 1) / 2}\)。

可以发现我们现在可以描述一个连通块的组合结构了，对这个结构作有标号 \(\text{Set}\) 构造即得答案。答案即为

\[\left[\frac{x^{n - m}y^m}{(n - m)! m!}\right] \exp\left( e^y - 1 + \sum_{i, j\ge 0} f_i(2^i - 1)^j2^{j(j - 1) / 2}\frac{x^iy^j}{i!j!} \right)
\]

这个大概可以通过直接操作 bgf 的系数并牛顿迭代得到 \(O(n^2 \log n)\) 的复杂度。没写呢。