Count Disjoint Subsequence Pairs with Equal GCD

# Count Disjoint Subsequence Pairs with Equal GCD ### Problem Given a positive integer array `nums`, count ordered pairs of nonempty subsequences `(seq1, seq2)` such that: - No original index belongs to both subsequences. - The greatest common divisor of `seq1` equals that of `seq2`. Each subsequence retains its selected indices in their original order. An index may be unused. Different choices of indices count separately, even when their selected values are identical. The two subsequences have distinct roles, so swapping their index selections gives a different ordered pair. Return the count modulo `10^9 + 7`. ### C++ Interface ```cpp class Solution { public: int subsequencePairCount(vector<int>& nums); }; ``` ### Examples #### Example 1 **Input:** `nums = [2,2,3]` **Output:** `2` **Explanation:** Put index `0` in the first subsequence and index `1` in the second, or swap these choices. Both GCDs are `2`. Index `2` is unused. No other disjoint nonempty pair has equal GCDs. #### Example 2 **Input:** `nums = [3,3,3]` **Output:** `12` **Explanation:** Every nonempty selection has GCD `3`. Using exactly two indices gives `3 * 2 = 6` ordered pairs: choose the unused index and then assign the other two to the two subsequences. Using all three indices gives `2^3 - 2 = 6` assignments with both subsequences nonempty. The total is `12`. ### Constraints - `1 <= nums.size() <= 200` - `1 <= nums[i] <= 200` ### Clarifying Questions - May the two subsequences contain the same value? Yes, if those occurrences come from different original indices. - Must every index be selected? No, unused indices are allowed. - Are empty subsequences valid? No, both must be nonempty. - Is this an unordered pair count? No. The first and second subsequences are distinguished. ### What a Strong Answer Covers - Counts original index selections with disjointness and both nonempty requirements enforced. - Preserves the distinction between ordered pairs and repeated value sequences. - Justifies every counted pair and avoids counting a selection more than once. - Gives time and space bounds for the full input limits and handles the required modulus safely. ### Follow-up Questions - What should the answer be for a one-element array? - How can you check the count when every input value is the same? ```hint Decide the role of one index An index can be unused, belong to the first subsequence, or belong to the second. Track enough information about both partial subsequences to decide whether their final GCDs agree. ```