同构树计数 [构造]

$同构树计数$

$1 le T le 10^4, 1 le K le 10^{18}$

---

$color{red}{正解部分}$

首先要知道一棵树的同构数量 $x$ 可以表示为 $x = prod a_i! (a_i in N)$,
如下图为一个例子,

!/

于是考虑将 $K$ 分解为若干个菊花图, 使得两两菊花图之间互不对称, 使得每个菊花子树大小的阶乘乘起来为 $K$, 如下图所示,

为了防止子树之间对称, 在链后方加两个点 .

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 100005;

int cnt;
int flag;
int size[maxn];

ll K;
ll fac[maxn];

void DFS(ll now, int k){
        if(now == 1 || flag){ flag = 1; return ; }
        for(reg int i = k; i >= 2; i --){
                if(now % fac[i]) continue ;
                size[++ cnt] = i; DFS(now/fac[i], i);
                if(flag) return ; size[cnt --] = 0;
        }
}

void Work(){
        scanf("%lld", &K);
        if(K == 1){ printf("1
"); return ; }
        flag = cnt = 0; DFS(K, 19);
        if(!flag){ printf("-1
"); return ; }
        int sum = 2;
        for(reg int i = 1; i <= cnt; i ++) sum += size[i] + 1;
        printf("%d
", sum);
        for(reg int i = 1; i < cnt; i ++) printf("%d %d
", i, i + 1);
        int node_cnt = cnt;
        for(reg int i = 1; i <= cnt; i ++)
                for(reg int j = 1; j <= size[i]; j ++) printf("%d %d
", i, ++ node_cnt);
        printf("%d %d
", cnt, ++ node_cnt);
        printf("%d %d
", node_cnt, node_cnt + 1);
}

int main(){
        fac[0] = 1; for(reg int i = 1; i <= 20; i ++) fac[i] = 1ll*fac[i-1]*i;
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}