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

Автор ez_zh, история, 6 лет назад, По-английски

Problem link: AGC005D

You can use DP to solve this problem in O(NK).

This code got AC when N<=2000 and K<=N-1.

DP Solution (29ms)

Here is the editorial: Editorial

After I read the editorial, which explains the DP solution, I found this line below:

おまけ: 以上の考察をもう少し進めると、この問題は O(NlogN) で解くことが出来ます。

That means there is a faster way to solve this problem.

My friends has just found a NTT solution. It works in O(NlogN).

NTT Solution (2ms)

I hope it will be useful!

Happy coding!

  • Проголосовать: нравится
  • -36
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

orz zh

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

so how can you solve it?

Can you explain how to use $$$NTT$$$?

Greatful thanks to you.