C++で解く「因数から構成できる二分木」の総数を求めるアルゴリズム

問題概要

1より大きい正整数のリストが与えられます。これらの整数を使って二分木を構築することを考えます。ただし、同じ数は何度でも使用でき、葉以外のすべてのノードは、その2つの子ノードの値の積になっていなければなりません。この条件を満たす二分木が全部で何通り作れるかを求め、答えは 10⁹ + 7 で割った余りとして返します。

たとえば入力が [2, 4, 5, 10] の場合、答えは 7 になります。具体的には次の7通りの木が作れます。

• [2]
• [4]
• [5]
• [10]
• [4, 2, 2]（根が4、子が2と2）
• [10, 2, 5]（根が10、子が2と5）
• [10, 5, 2]（根が10、子が5と2）

解法のアプローチ：動的計画法（DP）

この問題は動的計画法で効率よく解けます。あらかじめ配列を昇順にソートしておけば、ある値を処理する時点で、その約数となる小さい値のDP値はすでに確定しています。そのため、積の組み合わせを素早く数え上げることができます。

手順は以下の通りです。

• キーを配列の値、値を「その値を根とする二分木の本数」とするマップ dp を用意する
• 配列 A をソートし、n := A のサイズ、ret := 0 と初期化する
• i を 0 から n − 1 まで繰り返す
  • dp[A[i]] を 1 増やす（単独の葉として使えるため）
  • j を 0 から i − 1 まで繰り返す
    • A[i] % A[j] == 0 のとき（A[j] が A[i] の約数のとき）
      • dp[A[i]] := dp[A[i]] + dp[A[j]] × dp[A[i] / A[j]]
  • ret := ret + dp[A[i]]
• ret を返す

ここで dp[A[j]] × dp[A[i] / A[j]] は、「左の子が A[j]、右の子が A[i] / A[j] となる組み合わせ」の総数を表しています。2つの因子が異なる値なら左右の入れ替えが別カウントされ（例：10 = 2 × 5 と 10 = 5 × 2）、同じ値なら自然に1通りだけ数えられる（例：4 = 2 × 2）ため、重複や漏れなく木の総数を求められます。

計算量

ソートに O(n log n)、約数のペア確認のための二重ループに O(n²) かかるため、全体の時間計算量は O(n²) です。空間計算量は、マップに各値ごとのDP値を保持するため O(n) となります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
int add(lli a, lli b){
    return ((a % MOD) + (b % MOD)) % MOD;
}
int mul(lli a, lli b){
    return ((a % MOD) * (b % MOD)) % MOD;
}
class Solution {
    public:
    int numFactoredBinaryTrees(vector<int>& A) {
        unordered_map <int, int> dp;
        sort(A.begin(), A.end());
        int n = A.size();
        int ret = 0;
        for(int i = 0; i < n; i++){
            dp[A[i]] += 1;
            for(int j = 0; j < i; j++){
                if(A[i] % A[j] == 0){
                    dp[A[i]] = add(dp[A[i]], mul(dp[A[j]], dp[A[i] / A[j]]));
                }
            }
            ret = add(ret, dp[A[i]]);
        }
        return ret;
    }
};
main(){
    vector<int> v1 = {2,4,5,10};
    Solution ob;
    cout << (ob.numFactoredBinaryTrees(v1));
}

add 関数と mul 関数は、大きな数同士の演算でオーバーフローが起きないよう、毎回 MOD（10⁹ + 7）で剰余を取るヘルパー関数です。dp マップには「その値を根とする二分木の本数」が格納されており、約数の関係にあるペアを見つけるたびに、子の組み合わせの数を掛け合わせて加算していきます。

入力

[2,4,5,10]

出力

7