Permutation Counting
Contest: Educational Codeforces Round 127 (Rated for Div. 2)
Difficulty rating: 2700
Tags: brute force, combinatorics, dp, fft, math

Calculate the number of permutations $$$p$$$ of size $$$n$$$ with exactly $$$k$$$ inversions (pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$p_i > p_j$$$) and exactly $$$x$$$ indices $$$i$$$ such that $$$p_i > p_{i+1}$$$.

Yep, that's the whole problem. Good luck!

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of test cases.

Each test case consists of one line which contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 998244352$$$; $$$1 \le k \le 11$$$; $$$1 \le x \le 11$$$).

Output format:
For each test case, print one integer — the answer to the problem, taken modulo $$$998244353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
5
10 6 4
7 3 1
163316 11 7
136373 11 1
325902 11 11

Example output:
465
12
986128624
7636394
57118194

Editorial:
A lot of solutions which were written during the contest use Berlekamp-Messey or some other algorithms related to analyzing linear recurrences, but the model solution is based on other principles.
First of all, if the number of inversions is at most $$$11$$$, it means that most elements of the permutation will stay at their own places, and those which don't stay at their places can't be too far away from them.
Let's denote a block $$$[l, r]$$$ in a permutation as a segment of indices $$$[l, r]$$$ such that:
• all elements less than $$$l$$$ are to the left of the block;
• all elements greater than $$$r$$$ are to the right of the block;
• all elements from $$$[l, r]$$$ belong to the block.
Let's say that a block is non-trivial if it contains at least two elements.
Suppose we split a permutation into the maximum number of blocks. Then, for each block, we can see that:
• if its length is $$$b$$$, it has at least $$$b-1$$$ inversions (to prove it, you can use the fact that the number of inversions is equal to the number of swaps of adjacent elements required to sort the permutation; and if we cannot split the block into other blocks, it means that we have to swap each pair of adjacent elements in it at least once to sort it)
• if the block is non-trivial, it has at least one $$$i$$$ such that $$$p_i > p_{i+1}$$$.
From these two facts, we can see that:
• there will be at most $$$11$$$ non-trivial blocks;
• there will be at most $$$22$$$ elements in total belonging to non-trivial blocks;
• the maximum possible length of a block is $$$12$$$.
The main idea of the solution is to calculate the following dynamic programming: $$$dp_{i,j,a,b}$$$ is the number of ways to split $$$j$$$ elements into $$$i$$$ non-trivial blocks such that there are exactly $$$b$$$ inversions in them and exactly $$$a$$$ pairs $$$p_i > p_{i+1}$$$. Then, to get the answer for the test case "$$$n$$$ $$$k$$$ $$$x$$$", we can iterate on the number of non-trivial blocks and the number of elements in them, and choose the elements belonging to that blocks with a binomial coefficient.
The only thing that's left is how to calculate this dynamic programming efficiently. There are a few ways to do it, but the model solution uses a table $$$cnt_{a,b,c}$$$ — the number of different non-trivial blocks of length $$$a$$$ with $$$b$$$ elements $$$p_i > p_{i+1}$$$ and $$$c$$$ inversions — to handle transitions. This table is not very big, so you can run an exhaustive search for $$$2$$$-$$$3$$$ minutes to calculate it and then just paste its results into the source code of your program. Note that you have to make sure that you consider only the blocks which cannot be split any further.