Share your approach for EXUNE

Can someone please share your approach for EXUNE.

4 Likes

Hi, I am the problem author. I will be writing an editorial shortly but the idea is as follows:

For n = 1, just output \frac{P(1)+P(-1)}{2}. Adding P(1) and P(-1) cancels out all the odd power terms and adds the even power terms twice.

For n > 1, you have to sum P(x_1,x_2,\ldots,x_n) over all the 2^n values where x_i \in \{-1,1\} and divide the answer by 2^n to get the required value. Try to prove this. You can find the sum in O(n\log{m}) by observing that P takes the value (k + n - 2i)^m \binom{n}{i} times in this sum.

7 Likes

I had a similar approach for subtask but didn’t figure it that it would be similar in 100pt solution also

1 Like

for n =1 P(1) = (k+x)^m I did using binomial expansion and found series like this
mC0 X k ^m + mC2 X k^(m-2) and so on… but it gives tle :frowning:

1≤m≤10^6
1≤T≤10^3

can you please comment here once the editorial is ready ?

1 Like

I saw your solution can you please brief a little about it.

Its same as author. Just that I took (1+x1/k+x2/k+...xn/k) and multiplied by k^m at last.

I also did almost same but why I get tle’s :weary::weary::weary:

Here you go, Editorial.

1 Like