Original link: https://www.shuizilong.com/house/archives/luogu-p4708-%E7%94%BB%E7%94%BB/
Title meaning
Unlabeled Euler graph count
analyze
The method is basically the same as 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(ns, 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; l = *it;
c = 1;
}
else {
++c;
}
}
z /= Fact;
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;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p4708-%E7%94%BB%E7%94%BB/
This site is only for collection, and the copyright belongs to the original author.