We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Polynomial Division
Polynomial Division
Sort by
recency
|
6 Discussions
|
Please Login in order to post a comment
This is my python Solution
the method is easy, but the debugging took me forever. O(n + qlog(n)) using fenwick trees
I worked sythentic division (very slow), reaching a point of root check -b/a and brute force computing sub polynomials (still too slow), then precomputing polynomial with possible root -b/a as a basis for root checking sub polynomials, and then integrating binary search tree on coefficient index updated values (per query) which is still too slow. Fenwick tree is a key prefix data structure for mutating polynomial coefficients and pertinent sub polynomials on query set. Recall summation difference between front and tail of sub polynomial, once polynomial array (including query updates) is computed and allows for rapid computation on subpolynomial summation series. Also worth noting this is computed (per large integers) on modulus p, so rationals on the set of reals need to be converted to integers mod p. That is computing for a/b compute b^-1 to compute a*b^-1%p.
here is hackerrank polynomial division solution
what does the following part of the code do; int coef = (MOD - mul(B, modPow(A, MOD - 2))) % MOD; pw[0] = 1; for (int i = 1; i <= T; i++) pw[i] = mul(pw[i - 1], coef);