HIGHINT - Editorial

general
, , ,
1

Links
Contest
Practice

Author: Abhishek Kanhar
Tester: Devanshu Agarwal
Editorialist: Devanshu Agarwal

DIFFICULTY:

Hard

PREREQUISITES:

NTT, Multi-point Evaluation

EXPLANATION:

We have to find the answer modulo 786433 = 3*2^18+1, that’s the first hint that we have to use NTT

O(N2log2N) Solution

Lets find the probability that **B1** is included in the expected sum, the required answer is, **B1** * **P1** (probability to select **K-1** barmen from the rest **N-1**).

The probability to select K-1 barmen from the rest N-1, can be calculated using NTT, we simply have to calculate the power of K-1 in the polynomial,
(1 - P2 + P2x) * (1 - P3 + P3x) * … * (1 - Pn + Pnx)
This can be calculated in O(Nlog2N), using Divide and Conquer with NTT technique.
Finally, we calculate the probability that we include Bi for all i , and sum them.

O(Nlog2N + MOD*logN) Solution

Let us define F(x) = (1 - P1 + P1x) * (1 - P2 + P2x) * (1 - P3 + P3x) * … * (1 - Pn + Pnx).
The required answer is thus sum of Bi * Pi * (coefficient of Xk-1 in F(x) / (1 - Pi + Pix))
= sum Bi * Pi / (1 - Pi) * (coefficient of Xk-1 in F(x) / (1 + Hix)), where Hi = Pi / (1 - Pi)
= sum Bi * Pi / (1 - Pi) * (coefficient of Xk-1 in F(x) * (1 - Hix+Hi2x - Hi3x …))
= sum Bi * Pi / (1 - Pi) * (coefficient of Xk-1 in (1 + C1x+C2x2 + C3x3 …) * (1 - Hix+Hi2x - Hi3x …)), where Ci is coefficient of xi in F(x).
= sum Bi * Pi/ (1 - Pi) * (C0 * (-1)K * HiK + C1 * (-1)K-1 * HiK-1 …)
= sum Bi * Pi / (1 - Pi) * G(Hi), where G(x)= (C0 * (-1)K * xK + C1 * (-1)K-1 * xK-1 …)
= B1 * P1/ (1 - P1) * G(H1) + B2 * P2 / (1 - P2) * G(H2) + …

The polynomial F(x) can be constructed in Nlog2(N) using Divide and Conquer + NTT and thus G(x) can be constructed in O(N).
G(Hi) can be calculated for all i in MOD*log(N) using NTT.
Refer Here.

Author’s Solution can be found here
3 Likes
2

Can also be done in Nlog^2(N) . A polynomial sum of the form \displaystyle \sum \dfrac{a_i}{b_ix+c_i} can be found using polynomial fractions and divide and conquer. Link to solution

4 Likes
3

From your solution I understand that (correct me if I’m wrong) the answer will be \displaystyle \prod_{i=1}^{N} p_i times the coefficient of x^{k-1} in the numerator of

\sum_{i=1}^{N} \frac{B_i}{\frac{1-p_i}{p_i} + x}

where p_i = P_i / Q_i is the probability. It surely works but how did you reach this conclusion?

4

From the editorial,
ans=sum of Pi * Bi * (coefficient of Xk-1 in F(x) / (1 - Pi + Pix))
= sum of (coefficient of Xk-1 in (F(x) * Pi * Bi)/ (1 - Pi + Pix))
= coefficient of Xk-1 in F(x) * sum (Pi * Bi)/ (1 - Pi + Pix)
the denominator of sum Pi * Bi/ (1 - Pi + Pix) is F(x),
=coefficient of Xk-1 in numerator of sum Pi * Bi/ (1 - Pi + Pix)
thus the answer. @meooow

1 Like
5

Ah I get it, thanks. My fault for writing the sum in a hard to recognize form. Putting it as you say makes it easier to recognize.

\sum_{i=1}^{N} \frac{p_iB_i}{1 - p_i + p_ix}

Doesn’t this mean that in your editorial’s explanation you meant to write p_i B_i instead of just B_i?

6

Yes, will correct it by tomorrow.