YouKn0wWho's blog

I heard You are good at POLYNOMIALS
By YouKn0wWho, 5 years ago, In English

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$$$?

  • Vote: I like it
  • +49
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -38 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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)$$$.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -93 Vote: I do not like 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?

→ Reply