Please help me with this problem

Revision en1, by SkippedSolution, 2023-10-29 05:50:14

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English SkippedSolution 2023-10-29 06:08:01 37
en2 English SkippedSolution 2023-10-29 05:51:07 0 (published)
en1 English SkippedSolution 2023-10-29 05:50:14 559 Initial revision (saved to drafts)