Problem L is equivalent to number of correct bracket sequences length of 2*n. Answer for this is Catalan number.

In problem M you could notice, that K! = 0 mod M for all K >= M, because M = 0 mod M and (n+1)! = (n + 1) * n!. So, answer for n > 12 is 0, otherwise we compute factorials

Allow me to ask you some questions:

1. What does "solve for a given $$$(T(x), L, R)$$$" mean exactly? Is it to find the coefficient of $$$x^0$$$ in $$$T(x) P_{[L,R]}(1/x)$$$ given the first $$$R-L+2$$$ coefficients of $$$T(x)$$$?
2. About "We only need to maintain the first $$$R-L+2$$$ coefficients", I think we need to compute $$$N$$$ coefficients of $$$T(x)$$$ anyway because we need to solve for $$$(T(x), 1, N)$$$. If so, what makes us compute $$$T(x)$$$'s coefficients without multipoint evaluation?

You can find that for all 4 possible consecutive two elements (i.e. 00,01,10,11) one of the following is always true:
· picking left element <-> apply AND operator, and picking right element <-> apply OR operator;
· picking left element <-> apply OR operator, and picking right element <-> apply AND operator.

Yeah in our team only one guy is really good with FFT and the rest of us were just: O_O

For each $$$1 \le i \le K$$$, consider the "boundary line" between the squares $$$\le i$$$ and $$$> i$$$ (from bottom-left corner to top-right corner), and shift the $$$i$$$-th path $$$1$$$ unit to the right and $$$1$$$ unit downwards. If there were no $$$A_{R,C} = V$$$ condition, then the problem is just counting set of disjoint paths with some set of starting points and ending points that can be solved using Lindstrom-Gessel-Viennot Lemma.

To handle the $$$A_{R,C}=V$$$ condition, note that it is equivalent to saying that $$$V-1$$$ paths continue on the "top-left" of some point $$$p$$$ in the lattice and the other paths continue on the "bottom-right" of the same point $$$p$$$. To keep track of this information, instead of setting all edge weights as $$$1$$$ in LGV Lemma, set the edges adjacent to $$$p$$$ as $$$0$$$ and then for the row of edges below $$$p$$$, set the left side as $$$1$$$ and right side as $$$x$$$. This will multiply the weight all paths that go from the bottom-right by $$$x$$$. By LGV Lemma, you just need to find the determinant of the matrix, which is a polynomial in $$$x$$$. To find it fast, substitute values and use Lagrange Interpolation.

This is definitely a bit of a strange concept, I think you should look at the linked paper for more details.

The original problem can be thought of as a linear transformation of given $$$[x]$$$, find the values $$$[Z_1 x, Z_2 x, Z_3 x, \ldots, Z_k x]$$$, which is just a left-multiplication by a $$$k \times 1$$$ matrix. The transpose then, is given $$$[D_1, D_2, \ldots, D_k]$$$, find $$$[\sum_{i=1}^k D_i Z_i]$$$, which is multiplying by the $$$1 \times k$$$ matrix. Then, we can essentially take any algorithm which solves the transposed problem and "reverse+transpose" it to get a solution to the former; this is because we can treat the algorithm as a sequence of linear transformations, and $$$(AB)^T = B^TA^T$$$. It is definitely a little strange, but seems like a pretty interesting concept to me.

Wow, 17234ms in my poor computer and 1824 ms in Codeforces!

I realized that the first question is silly.

Now imagine a path from $$$(0,0)$$$ to $$$(p,Ap+B)$$$ (let's denote this part of the path by $$$u$$$) and then to $$$(W,H)$$$ (denote this by $$$v$$$).

Consider paths shaped like $$$u+\uparrow+v$$$, they are exactly all the paths from $$$(0,0)$$$ to $$$(W,H+1)$$$. $$$p$$$ indicates the last time for them to touch $$$y=Ax+B$$$. (it is obvious that it must go $$$\uparrow$$$ after touching $$$y=Ax+B$$$ for the last time, or it will never reach $$$(W,H+1)$$$ since $$$(W,H+1)$$$ is above $$$y=Ax+B$$$)

This also explained why $$$z$$$ does not depend on $$$A$$$ or $$$B$$$, because $$$A$$$ and $$$B$$$ only effect how we classify these paths.

Why downvote?