题意

无标号欧拉图计数

分析

做法基本和 SGU 282. Isomorphism 一样。

#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;
}

VII adj[N];
int w[N]; bool vis[N];
int sw, sz;

void dfs(int u) {
    vis[u] = 1;
    sw += w[u]; sz += 1;
    for (auto e: adj[u]) {
        int v = e.fi; //w = e.se;
        if (!vis[v]) dfs(v);
    }
}

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] - 1) / 2;
        if (!(P[i]&1)) w[i] += 1;

        REP(j, i) {
            int d = __gcd(P[i], P[j]);
            int ei = P[j] / d, ej = P[i] / d;
            if (ei&1) {
                if (ej&1) {
                    adj[i].PB({j,0});
                    adj[j].PB({i,0});
                    z += d;
                } else {
                    w[i] += d;
                }
            } else {
                if (ej&1) {
                    w[j] += d;
                } else {
                    z += d;
                }
            }
        }
    }

    REP(i, SZ(P)) if (!vis[i]){
        sw = 0; sz = 0; dfs(i);
        z += max(sw-1, 0) - (sz-1);
    }
    return z;
}

int main(){

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

    MOD = 998244353;

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

    gen();

    Int res = 0; ECH(it, Partition){
        res += c(*it) * pow(Int(2), g(*it));
    }
    res /= Fact[n];
    cout << res << endl;
}

Posted by xiaodao
Category: 日常