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!
orz zh
so how can you solve it?
Can you explain how to use $$$NTT$$$?
Greatful thanks to you.