PROBLEM LINK:
Author: Anay Karnik
Testers: Shashwat Chandra, Bharat Goyal, Taranpreet Singh
Editorialist: Anay Karnik
DIFFICULTY:
Medium
PREREQUISITES:
Basics of polynomial expansion, binomial coefficients, modular exponentiation
PROBLEM:
Let P be a polynomial in n variables given by:
Here n, k and m are positive integers. Find the sum of all coefficients of the terms of the polynomial which have even powers in each of the n variables and output it modulo 10^9 + 7.
QUICK EXPLANATION:
Find the sum of all values of P(x_1, x_2, \ldots,x_{n}) where x_i \in \{-1, 1\} and divide it by 2^n to find the answer. Find this in O(n \log m) by considering how many times each value repeats.
EXPLANATION:
Let’s first solve the problem for n = 1. We can divide the terms of the polynomial in 2 categories, terms with even powers and terms with odd powers. We observe that P(1) is the sum of all coefficients of terms of the polynomial and P(-1) is the sum of coefficients of terms with even powers subtracted by the sum of coefficients of terms with odd powers. Thus the required sum will be:
Now let’s try to generalize this for any n. Say we divide the terms of the polynomial in 2^n categories according to the parities of the powers of the n variables
For a particular value of P(x_1,x_2,,x_n) where x_i \in \{1,-1\}, we see that terms of a particular category are either added or subtracted depending on whether the number of variables having odd power in the term and having value = -1 are even or odd respectively.
Consider the sum S of all 2^n values of P(x_1,x_2,\ldots,x_n) where x_i \in \{1,-1\}. Observe that the terms with even powers in all the variables will always be added. Thus, they will appear 2^n times. For terms of any other category, say a category with i > 0 variables having odd powers, the terms will be added if j of these i terms have value -1 where j is a even number. Thus, the terms will be added A times where,
And the terms will be subtracted B times where,
But we know
This has various proofs.
Thus, these terms will be added and subtracted equal number of times and the final sum S will just be equal to 2^n times the sum of coefficients of all terms with even powers in all the variables. Our required sum will then be \frac{S}{2^n}.
We can find S in O(n \log{m}) by observing that the value (k + n - 2i)^{m} appears {n}\choose{i} times.
SOLUTIONS:
This was my first time setting a problem, so I hope you enjoyed it. I would love to hear your thoughts on it.