Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### YouKn0wWho's blog

By YouKn0wWho, 7 months ago, ,

Let's say we have a polynomial $P(x)$ in the field modulo $(10^9+7)$

$P(x)=\prod_{i=0}^{n}{(a_i*x^i+b_i)}$

For $n=10^5$ obviously we can't generate the whole polynomial explicitly. But I think maybe we can solve the following problems

• Find the coefficient of $x^k$ in $P(x)$
• Find the polynomial $P(x)\%x^k$

I don't how to solve them efficiently. That's why I am asking you guys. How efficiently can you solve the problems for some $k$?

• +49

 » 7 months ago, # |   -38 For $k = O(n)$ both problems are trivial. You can do divide and conquer, and FFT, and each step keeping atmost first k coefficients, taking $O(n log ^2 n)$ time.
•  » » 7 months ago, # ^ |   +6 Why do you think it will have this complexity? It will be $O(nk \log k)$It seems that it is more or less general knapsack problem, I don't think you can do much better than $O(nk)$.
•  » » 7 months ago, # ^ |   -20 OK, you deleted your comment, but I SAW EVERYTHING. So I can answer.Wow, cool accusations. Do you mean "Did you read my comment, I do divide and conquer" or "Do you even know divide and conquer, it is a cool technic that solves any problem on array with $O(\log)$ overhead if you can solve the same problem with 2 elements"?It seems that you want to do $O(n)$ multiplications of $O(k)$ degree polynomials using FFT, if my math is right, it is $O(nk \log k)$. If you still think that I'm wrong, please elaborate on your solution.
•  » » » 7 months ago, # ^ |   +37 I deleted the comment because i realised i was wrong and the complexity is indeed $O(nklogk)$.The good thing is that since "YOU SAW EVERYTHING", and decided to elaborate, others who might have the same confusion can see it.
 » 7 months ago, # | ← Rev. 2 →   -93 While we are on the topic of polynomials, you might as well try my polynomial problem:Anay and PolynomialIt's a nice problem with an elegant solution of $40$ lines!Edit: Why the downvotes?