I'm having problems understanding how to solve this problem https://atcoder.jp/contests/abc156/tasks/abc156_d

I've seen a lot of solutions, I've checked almost everything on the internet but nothing helps me because I simply don't understand a single algorithm used in this problem.

I've never used fast exponentiation, extended euclidean algorithm, inverse modulo, lucas theorem or whatever other algorithm I need for this problem before, and I'm having problems understanding what to use, which to use, and how to implement it.

I understand fast exponentiation and I think I can calculate 2^N in this problem, but I don't how to calculate binomial coefficients of N over a and N over b, could anyone help ?

And please understand that I'm really unfamiliar with these kinds of math problems, but I'm starting to learn them, so please make implementation as simple as possible.

For a given array $$$a_i$$$ , we need to find all subsets withing given range [A,B].

For an array consisting of $$$a_1$$$ and $$$a_2$$$ all subsets are: {},{$$$a_1$$$},{$$$a_2$$$},{$$$a_1$$$,$$$a_2$$$}.

Their sums are 0, $$$a_1$$$, $$$a_2$$$, $$$a_1$$$+$$$a_2$$$.

Input:

3 -1 2
1 -2 3

Output:

5

The 5 subsets that fit between -1 and 2 are : {} , {$$$a_1$$$},{$$$a_1$$$,$$$a_2$$$},{$$$a_1$$$,$$$a_2$$$,$$$a_3$$$},{$$$a_2$$$,$$$a_3$$$}.

I did the math and I think I got the task, I got how to solve it, I just don't know how to implement it.

My way is calculating the sum of all elements, and then reducing each element at a time to produce more subsets, and from those subsets to produce even more (unique of course) subsets, all while checking if each subset is within range of given [A,B], but I don't know how to implement it, I've never done this type of a task before. My way would have time complexity of O(2^n) and constraints on this program are 1<n<=34, -2e7 <= $$$a_i$$$ <= 2e7, -5e8 <= $$$a_i$$$ <= 5e8, would this even pass theoretically ?

There is a square 3x3 consisting of 9 natural numbers. The sum of every row, every column and both diagonals are mutually the same (row 1 has the same sum as row2, row3, column1, column2 etc.).

Some numbers were deleted from the square (deleted numbers are numbered as 0) and the task is to restore those numbers. It is guaranteed that the task is solvable and that there will never be more than 3 deleted numbers. All numbers are less than 20000.

Input:

5 10 3 
4 0 8                   
9 2 7

Output:

5 10 3
4 6 8
9 2 7

Input:

0 11 11
15 9 0
7 7 13

Output:

5 11 11
15 9 3
7 7 13

Input:

496 469 0
0 523 415
442 0 550

Output:

496 469 604
631 523 415
442 577 550

I have some ideas, and I've tried to do the task, but my way wouldn't work on all test cases.