# 某岛

… : "…アッカリ～ン . .. . " .. .
May 23, 2023

# AtCoder Beginner Contest 284

## Ex. Count Unlabeled Graphs

k = 1 的情况下，显然就是无标号图计数。

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

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

```