• https://oeis.org/A001349
• Weisstein, Eric W. “Euler Transform.” From MathWorld–A Wolfram Web Resource.
• 题解 P5900 【无标号无根树计数】

没找到相关的题目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(n-s, 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[c]; l = *it;
            c = 1;
        }
        else{
            ++c;
        }
    }

    z *= invFac[c];
    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[i-j];
    }

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

Posted by xiaodao
Category: 日常