EXUNE - Editorial

PROBLEM LINK:

Practice
Contest

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:

P(x_1, x_2, \ldots,x_{n}) = (k + x_1 + x_2 + \cdots + x_{n})^{m}

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:

\frac{P(1)+P(-1)}{2}

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,

A = \sum_{2j \leq i}{ {i}\choose{2j} }

And the terms will be subtracted B times where,

B = \sum_{2j+1 \leq i}{ {i}\choose{2j+1} }

But we know

\sum_{2j+1 \leq i}{ {i}\choose{2j+1} } = \sum_{2j \leq i}{ {i}\choose{2j} } = 2^{i-1}

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:

Commented Code

This was my first time setting a problem, so I hope you enjoyed it. I would love to hear your thoughts on it.

7 Likes

where’s the editorial for EXUND ???

Great problem. Really enjoyed solving it. Although I took a different approach involving generating functions.

My approach also allows you to solve it when n is large ( say \sim 10^9 ) but m is small ( say \sim 10^5 ).

The same question but with the modified constraints can’t be solved with your approach @karnikanay so do give it a try!

1 Like

Hey, I am glad you enjoyed the problem.

I had tried solving it for small m and large n but couldn’t find any solutions so I increased the constraints on m. Didn’t think of generating functions though. I will give it a try. Do you mean multivariate generating functions or generating function for m, treating n and k as constants?

@karnikanay
The latter.

But an exponential generating function instead.

1 Like

@karnikanay The editorial link on the problem page does not point here. It would be great if you could get it fixed.

1 Like