Chips on a Line
Contest: Educational Codeforces Round 168 (Rated for Div. 2)
Difficulty rating: 2700
Tags: brute force, combinatorics, dp, greedy, math

You have $$$n$$$ chips, and you are going to place all of them in one of $$$x$$$ points, numbered from $$$1$$$ to $$$x$$$. There can be multiple chips in each point.

After placing the chips, you can perform the following four operations (in any order, any number of times):

- choose a chip in point $$$i \ge 3$$$, remove it and place two chips: one in $$$i-1$$$, one in $$$i-2$$$;
- choose two chips in adjacent points $$$i$$$ and $$$i+1$$$, remove them and place a new chip in $$$i+2$$$;
- choose a chip in point $$$1$$$ and move it to $$$2$$$;
- choose a chip in point $$$2$$$ and move it to $$$1$$$.

Note that the coordinates of the chips you place during the operations cannot be less than $$$1$$$, but can be greater than $$$x$$$.

Denote the cost of chip placement as the minimum number of chips which can be present on the line after you perform these operations, starting from the placement you've chosen.

For example, the cost of placing two chips in points $$$3$$$ and one chip in point $$$5$$$ is $$$2$$$, because you can reduce the number of chips to $$$2$$$ as follows:

- choose a chip in point $$$3$$$, remove it, place a chip in $$$1$$$ and another chip in $$$2$$$;
- choose the chips in points $$$2$$$ and $$$3$$$, remove them and place a chip in $$$4$$$;
- choose the chips in points $$$4$$$ and $$$5$$$, remove them and place a chip in $$$6$$$.

You are given three integers $$$n$$$, $$$x$$$ and $$$m$$$. Calculate the number of placements of exactly $$$n$$$ chips in points from $$$1$$$ to $$$x$$$ having cost equal to $$$m$$$, and print it modulo $$$998244353$$$. Two placements are considered different if the number of chips in some point differs between these placements.

Input format:
The only line contains three integers $$$n$$$, $$$x$$$ and $$$m$$$ ($$$1 \le m \le n \le 1000$$$; $$$2 \le x \le 10$$$).

Output format:
Print one integer — the number of placements with cost equal to $$$m$$$, taken modulo $$$998244353$$$.

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

Note:
In the first example, there are five ways to place $$$2$$$ chips in points from $$$1$$$ to $$$3$$$ so that the cost is $$$1$$$:

- $$$(1, 1)$$$;
- $$$(1, 2)$$$;
- $$$(1, 3)$$$;
- $$$(2, 2)$$$;
- $$$(2, 3)$$$.

Example input:
2 3 1

Example output:
5

Example input:
42 10 5

Example output:
902673363

Editorial:
The operations described in the statement are kinda similar to the identities for Fibonacci numbers, so maybe the solution will be connected to them.
Let's assign each chip placement a weight: if chips are placed in points $$$x_1, x_2, \dots, x_n$$$ (repeating if multiple chips are in the same position), the weight of this placement is $$$f_{x_1} + f_{x_2} + \dots + f_{x_k}$$$, where $$$f_i$$$ is the $$$i$$$-th Fibonacci number ($$$f_1 = f_2 = 1$$$; $$$f_{i+2} = f_i + f_{i+1}$$$).
We can show that two placements can be transformed into each other if and only if their weights are identical. First of all, the operations described in the statement don't change the weight, so two placements with different weights cannot be transformed into each other. To show how to transform two placements with identical weight into each other, let's bring them into "canonical" form as follows:
• while there is a chip with coordinate $$$i > 2$$$, convert it into two chips with coordinates $$$i-1$$$ and $$$i-2$$$;
• if all remaining chips are in points $$$1$$$ and $$$2$$$, move all chips from $$$2$$$ to $$$1$$$.
After performing this sequence of actions, we will transform a placement of chips into the form "all chips are in point $$$1$$$, and the number of these chips is equal to the weight of the placement". And since all operations we apply are invertible (for every operation, there is an operation which "rolls it back"), we can transform any placement to any other placement with the same weight through this "canonical form".
So, instead of counting the placements, let's group them according to their weights and work with them. For every possible weight of a placement (which is an integer from $$$1$$$ to $$$f_x \cdot n$$$), we need to answer two questions:
• Is it true that the minimum cost of a placement of this weight is exactly $$$m$$$?
• How many placements with this weight are there?
The former is simple: this is just checking that the minimum number of Fibonacci numbers used to represent an integer is equal to $$$m$$$. We can precalculate this minimum number of Fibonacci numbers to represent each integer with a simple dynamic programming.
The latter is a bit more tricky: we need to count the number of ways to represent the given number as a sum of exactly $$$n$$$ Fibonacci numbers from $$$f_1$$$ to $$$f_x$$$, where the order of these Fibonacci numbers does not matter. There are different ways to calculate it, the model solution uses a dynamic programming which uses $$$O(f_x \cdot n^2 \cdot x)$$$ time and $$$O(f_x \cdot n^2)$$$ memory.
Let $$$dp_{i,j}$$$ be the number of ways to partition the integer $$$i$$$ into $$$j$$$ Fibonacci numbers. Initially, we will consider the situation when we can't use any Fibonacci numbers, so $$$dp_{0,0} = 1$$$ and everything else is $$$0$$$. And then we will "add" Fibonacci numbers one by one, so first we will update our dynamic programming in such a way that we can only use $$$f_1$$$; then, only $$$f_1$$$ and/or $$$f_2$$$; and so on.
Let's show how to "update" our dynamic programming when we can use a new number $$$k$$$ in partitions. The simple way to do this is as follows: for every $$$dp_{i,j}$$$, iterate on the number $$$c$$$ of new elements we will use, and get a partition of integer $$$i + c \cdot k$$$ into $$$j+c$$$ numbers. However, that is too slow.
Instead, let's iterate on the states of our dynamic programming in ascending order of $$$i$$$, and in each state, add at most one element to the partition (so, increase $$$dp_{i+k,j+1}$$$ by $$$dp_{i,j}$$$). At the first glance, it only allows us to use one element equal to $$$k$$$; however, when we consider the state $$$dp_{i+k,j+1}$$$ we updated, it will already store both the partitions which didn't use elements equal to $$$k$$$, and the partitions which used at least one element equal to $$$k$$$ (which came from the state $$$dp_{i,j}$$$); and by transitioning from $$$dp_{i+k,j+1}$$$ to $$$dp_{i+2k,j+2}$$$, we will "expand" all these partitions.
If the previous paragraph is a bit unclear to you, you can try viewing it as a three-state dynamic programming of the form "let $$$dp_{i,j,k}$$$ be the number of partitions of $$$i$$$ into $$$j$$$ Fibonacci numbers from $$$f_1$$$ to $$$f_k$$$", where we dropped the third state of our dynamic programming in favor of maintaining only one layer and being more memory efficient.