Original link: https://www.shuizilong.com/house/archives/%E6%97%A0%E6%A0%87%E5%8F%B7%E8%BF%9E%E9%80%9A%E5% 9B%BE/
- https://oeis.org/A001349
- Weisstein, Eric W. “Euler Transform.” From MathWorld–A Wolfram Web Resource.
- Solution to P5900 【Unlabeled Unrooted Tree Counting】
No related topic found 0.0.
#include <lastweapon/poly>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(1e2) + 9;
VVI Partition; VI cur;
int n, m;
void gen(int 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);
}
}
Mint c(const VI P, int n){
Mint z = fac[n]; int c = 0, l = P.front();
ECH(it, P){
z /= *it; if (*it != l){
z *= invFac; l = *it;
c = 1;
}
else {
++c;
}
}
z *= invFac;
return z;
}
int g(const VI P){
int z = 0; REP(i, SZ(P)){
z += P[i] / 2; REP(j, i) z += __gcd(P[i], P[j]);
}
return z;
}
const int PMAX = int(1e2) + 9;
VI P; bitset<PMAX> isP; int mu[PMAX];
void sieve(){
mu[1] = 1; FOR(i, 2, PMAX){
if (!isP[i]) P.PB(i), mu[i] = -1;
for (int j=0;j<SZ(P)&&i*P[j]<PMAX;++j){
isP[i*P[j]]=1; if (!(i%P[j])){
mu[i*P[j]] = 0;
break;
} else{
mu[i*P[j]] = -mu[i];
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
sieve();
m = 2; n = 21;
Poly a(n), b(21);
FOR(i, 1, n) {
Partition. clear(); gen(i);
Mint z = 0; ECH(it, Partition) {
z += c(*it, i) * pow(Mint(m), g(*it));
}
z *= invFac[i];
b[i] = z;
}
Poly c(n);
FOR(i, 1, n) {
c[i] = i * b[i];
REP_1(j, i-1) c[i] -= c[j] * b[ij];
}
FOR(i, 1, n) {
REP_1(d, i) if (i % d == 0) {
a[i] += mu[i/d] * c[d];
}
a[i] /= i;
}
FOR(i, 1, n) {
cout << a[i] << " ";
}
cout << endl;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/%E6%97%A0%E6%A0%87%E5%8F%B7%E8%BF%9E%E9%80%9A%E5% 9B%BE/
This site is only for collection, and the copyright belongs to the original author.