PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Backtracking, Combinatorics, and Modular Arithmetic.
PROBLEM:
Given an array A of length N with some elements missing and a value S, consider all ways of filling missing elements and for every resulting array, find the sum of gcd of every unordered pair. Print the sum modulo 10^9+7.
SUPER QUICK EXPLANATION
- Order of elements does not matter. If C is the number of missing elements in the array and Si is the sum of non-missing elements, We need to fill C values so that their sum is S-Si.
- We can calculate all such ways by forming all ways, say in the array B of length C, such that B[i] \leq B[i+1] and counting all different ordering using combinatorics.
EXPLANATION
Considering the slow solution first.
We can make a backtracking solution where we try to fix the first x elements, and filling missing elements with all possible choices such that the total sum does not exceed S. Then iterating over every pair of values and calculate pairwise gcd-sum and print the answer. Time complexity, in this case, is Exponential, thus, will pass only the first subtask.
For the second subtask, we need to work harder than that.
First of all, Notice that the order of elements does not matter at all since the position of an element is irrelevant to our problem.
Second thing, If Si is sum of visible elements, Missing elements can have sum S-Si. Now, Suppose we have a parititon B_1, B_2, B_3 \dots B_k such that \sum B[i] = S-Si.
If we can get all partitions of S-Si into C elements, we can simply calculate the answer in O(N^2) by iterating over every pair and taking gcd.
But, Number of partitions of S is also very high if we consider them ordered. Like, If we consider 1+2 different than 2+1 as a partition of 3, Number of the partition of 50 is very high.
But, We can notice, that pairwise gcd-sum do not change, when just the ordering of elements of partition changes. Like, Suppose we have example N = 3, S = 4 and array 1 -1 -1. We can notice that pairwise gcd-sum of 1 1 2 is same as pairwise gcd-sum of 1 2 1. Hence, if we can calculate the pairwise gcd-sum for all distinct partitions of S-Si with non-missing elements, we can solve this problem fast enough.
Now, we can once again use backtracking solution, this time with another constraint, that current element cannot be smaller than the previous element. This way, we can get a partition and we calculate pairwise gcd-sum.
But, the problem is, how do we know how many times a partition will appear. Fortunately, we can rush to Combinatorics 
for answers. We can see, It is just the number of Distinct permutations of the given sequence.
Fortunately, If any element occurs x times, the Same permutation will be counted x times. This way, We can just Find the number of distinct permutations of the given sequence, and thus, find the required answer.
Hence, we can just find every unordered partition of S-Si into C elements, Find pairwise gcd-sum with each partition and also the number of times the same partition may appear and calculate the answer.
For reference, the method of computing distinct permutations of a sequence can be found here.
Time Complexity
The time complexity of this solution is O(P(S)*N^2) where P(S) is the number of unordered partitions of S. There is no closed form for Number of unordered partitions of a number, but for S = 50, it is small enough for our solution to pass comfortably.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
. Did anyone solve it by dp?