一个奇奇怪怪的图计数题

· · 个人记录

考虑一张 n 个点的无向图 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 的 sb 的 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 跑出来的 g 数组相同. n,m\leq 100.

考虑题目的条件是什么意思，就是任意两点之间要么不连通，要么直接相连，要么可以只通过前 n-m 个点相连. 把前 n-m 个点称为 A 类点，后 m 个点称为 B 类点，那么考虑最终图的一个连通块，如果它只含有 B 类点，那么它应该连成一个完全图，只有一种方案；否则，假设有 i 个 A 类点和 j 个 B 类点，那么 A 类点之间应该连通，并且每一个 B 类点应该向至少一个 A 类点连边，B 类点之间的边任意安排，这个方案数是 h_i(2^i-1)^j2^{j(j-1)/2}，其中 h_i 是 i 个点的无向连通图个数. 于是我们可以直接写出答案

G(z)=\sum_{i\geq 0}\frac{2^{i(i-1)/2}}{i!}z^i\quad H(z)=\ln G(z)=\sum_{i\geq 0}\frac{h_i}{i!}z^i ans=[(n-m)!m!x^{n-m}y^m]\exp\left(e^y-1+\sum_{i,j\geq 0}h_i(2^i-1)^j2^{j(j-1)/2}\frac{x^iy^j}{i!j!}\right)

那么直接做就是 O(n^4) 的，可以用多项式科技做到更好的复杂度.