Atcoder Problem

Please help me in this problem:

The first part of the editorial was clear to me, the second part(forming the dp) wasn’t clear, can someone help me in this?
@galencolin @carre @ssjgz @everule1

Sorry, I took a quick look at the problem and editorial just to realize that that’s not enough for me to come up with an answer. I hope tonight (it’s morning on this side of the word right now) I have time to look deeper and see if I can understand it.

You get the bipartite matching right?

The main idea is that the edges nicely give us 2k straight lines. 2 for each value mod k.
Like 1L - 4R - 7L and 1R-4L-7R.

To be clear 1L is node 1 on the left.

We can compute the number of ways to match j nodes in line of length l by dp of length, matches and whether the previous value is used.

Which will work in O(l^2).

I can’t figure the second dp, but you can use NTT.
There will at most be 3 different polynomials. M_ix^i for each line. So you can count the number of lines to use polynomial exponentiation for each type and multiply all to get the final M_i.

The dp is probably some knapsack variant, but I haven’t thought of the details yet. My current idea is O(N^3)