Блог пользователя YouKn0wWho

Автор YouKn0wWho, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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)$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -93 Проголосовать: не нравится

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?