Let's say we have a polynomial $$$P(x)$$$ in the field modulo $$$(10^9+7)$$$
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$$$?
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.
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)$$$.
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.
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.
While we are on the topic of polynomials, you might as well try my polynomial problem:
Anay and Polynomial
It's a nice problem with an elegant solution of $$$40$$$ lines!
Edit: Why the downvotes?