Ex. Count Unlabeled Graphs

k = 1 的情况下，显然就是无标号图计数。
所以做法也必然不会弱于 原题。

回忆原题中，我们对点集的对称群，按照 cycle index 进行分类，再去生成对应的边置换群，再得到边置换群的 cycle index。不过看起来这里我们既要考虑边染色，还要考虑点染色，好在它们的结构都是用初始的点群的 cycle index 所决定的，可以一起参与计算。

最后再 简单冗斥 一下即可。

#include <lastweapon/number>

using namespace lastweapon;

const int N = int(5e1) + 9;
Int Fact[N]; VVI Partition; VI cur;
int n;

void gen(int n = ::n, int s = 1){
    if (!n){
        Partition.PB(cur);
    }
    else if (n >= s){
        cur.PB(s); gen(n-s, s); cur.pop_back();
        gen(n, s+1);
    }
}

Int c(const VI P){

    Int z = Fact[n]; int c = 0, l = P.front();

    ECH(it, P){
        z /= *it; if (*it != l){
            z /= Fact[c]; l = *it;
            c = 1;
        }
        else{
            ++c;
        }
    }

    z /= Fact[c];
    return z;
}

int g(const VI P){

    REP(i, SZ(P)) {
        w[i] = 0; vis[i] = 0;
        adj[i].clear();
    }

    int z = 0; REP(i, SZ(P)){
        z += P[i] / 2;
        REP(j, i) z += __gcd(P[i], P[j]);
    }
    return z;
}

Int binom(int n, int m) {
    return Fact[n] / (Fact[m] * Fact[n-m]);
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int k; RD(n, k, MOD); Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;

    gen();

    Int z = 0; ECH(it, Partition) if (SZ(*it) >= k) {
        Int zz = 0;
        REP(i, k) {
            Int d = binom(k, i) * pow(Int(k-i), SZ(*it));
            if (i&1) zz -= d; else zz += d;
        }
        z += zz * c(*it) * pow(Int(2), g(*it));
    }
    z /= Fact[n];
    cout << z << endl;
}

Posted by xiaodao
Category: 日常