Given an array A of length n (n<=25) (Ai<=1e9). You have to construct a full binary tree with n nodes numbered from 1 to n, and if i is the parent of j and k, Ai=Gcd(Aj,Ak) must be satisfied. Two binary trees are considered different if two indexes i,j exist such that i is parent of j in this tree but not in the other. Count the number of distinct way to build the tree (in mod 1e9+7).
I tried to think of dp bitmask approach but the constraint for n seems too large for it. Is it solvable with DNC or not? Please help me.
I can only come up with dp bitmask in O(3^n) time complexity. For each mask t (which represent a subtree), I choose the minimum element to be the root r of subtree and iterate through all submasks of t^(1<<r) to divide the subtree in two smaller subtrees. I know O(3^n) isn't enough for n<=25 ,but hope it helps.
Well that's exactly what i expected to do. I just wonder if there is an optimization to remove unnecessary masks and improve time complexity. Thank you btw.