Original link: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-284/
Ex. Count Unlabeled Graphs
In the case of k = 1, it is obviously an unlabeled graph count.
So the practice will certainly not be weaker than the original question .
Recalling the original question, we classify the symmetry group of the point set according to the cycle index, and then generate the corresponding edge permutation group, and then obtain the cycle index of the edge permutation group. But it seems that here we have to consider not only edge coloring, but also point coloring. Fortunately, their structures are determined by the cycle index of the initial point group, and they can participate in the calculation together.
Finally, it’s just a matter of being redundant .
#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;
}
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[nm]);
}
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(ki), 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;
}
This article is transferred from: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-284/
This site is only for collection, and the copyright belongs to the original author.