Multiset of Strings
Contest: Educational Codeforces Round 132 (Rated for Div. 2)
Difficulty rating: 2500
Tags: bitmasks, brute force, dp, fft, flows, graphs, math, meet-in-the-middle, trees

You are given three integers $$$n$$$, $$$k$$$ and $$$f$$$.

Consider all binary strings (i. e. all strings consisting of characters $$$0$$$ and/or $$$1$$$) of length from $$$1$$$ to $$$n$$$. For every such string $$$s$$$, you need to choose an integer $$$c_s$$$ from $$$0$$$ to $$$k$$$.

A multiset of binary strings of length exactly $$$n$$$ is considered beautiful if for every binary string $$$s$$$ with length from $$$1$$$ to $$$n$$$, the number of strings in the multiset such that $$$s$$$ is their prefix is not exceeding $$$c_s$$$.

For example, let $$$n = 2$$$, $$$c_{0} = 3$$$, $$$c_{00} = 1$$$, $$$c_{01} = 2$$$, $$$c_{1} = 1$$$, $$$c_{10} = 2$$$, and $$$c_{11} = 3$$$. The multiset of strings $$$\{11, 01, 00, 01\}$$$ is beautiful, since:

- for the string $$$0$$$, there are $$$3$$$ strings in the multiset such that $$$0$$$ is their prefix, and $$$3 \le c_0$$$;
- for the string $$$00$$$, there is one string in the multiset such that $$$00$$$ is its prefix, and $$$1 \le c_{00}$$$;
- for the string $$$01$$$, there are $$$2$$$ strings in the multiset such that $$$01$$$ is their prefix, and $$$2 \le c_{01}$$$;
- for the string $$$1$$$, there is one string in the multiset such that $$$1$$$ is its prefix, and $$$1 \le c_1$$$;
- for the string $$$10$$$, there are $$$0$$$ strings in the multiset such that $$$10$$$ is their prefix, and $$$0 \le c_{10}$$$;
- for the string $$$11$$$, there is one string in the multiset such that $$$11$$$ is its prefix, and $$$1 \le c_{11}$$$.

Now, for the problem itself. You have to calculate the number of ways to choose the integer $$$c_s$$$ for every binary string $$$s$$$ of length from $$$1$$$ to $$$n$$$ in such a way that the maximum possible size of a beautiful multiset is exactly $$$f$$$.

Input format:
The only line of input contains three integers $$$n$$$, $$$k$$$ and $$$f$$$ ($$$1 \le n \le 15$$$; $$$1 \le k, f \le 2 \cdot 10^5$$$).

Output format:
Print one integer — the number of ways to choose the integer $$$c_s$$$ for every binary string $$$s$$$ of length from $$$1$$$ to $$$n$$$ in such a way that the maximum possible size of a beautiful multiset is exactly $$$f$$$. Since it can be huge, print it modulo $$$998244353$$$.

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

Note:
In the first example, the three ways to choose the integers $$$c_s$$$ are:

- $$$c_0 = 0$$$, $$$c_1 = 2$$$, then the maximum beautiful multiset is $$$\{1, 1\}$$$;
- $$$c_0 = 1$$$, $$$c_1 = 1$$$, then the maximum beautiful multiset is $$$\{0, 1\}$$$;
- $$$c_0 = 2$$$, $$$c_1 = 0$$$, then the maximum beautiful multiset is $$$\{0, 0\}$$$.

Example input:
1 42 2

Example output:
3

Example input:
2 37 13

Example output:
36871576

Editorial:
First of all, let's visualize the problem in a different way. We have to set some constraints on the number of strings which have some kind of prefix. Let's think about a data structure that would allow us to understand it better. One of the most common data structures to store strings which works with their prefixes and maintains the number of strings with some prefix is a trie; so, we can reformulate this problem using tries.
Now the problem is the following one: we have a binary trie of depth $$$n$$$; the leaves of this trie may store strings, and for each vertex except for the root, we can set a constraint on the number of strings stored in the subtree; what is the number of ways to choose these constraints so that the maximum number of strings (possibly with copies) the trie can store is exactly $$$f$$$? To handle it, we can use dynamic programming of the form $$$dp_{v,i}$$$ — the number of ways to choose the constraints for the vertex $$$v$$$ and its subtree so that the maximum number of strings which can be stored in the subtree is exactly $$$i$$$. When calculating $$$dp_{v,i}$$$, we can iterate on the constraint for the vertex $$$v$$$ (let it be $$$a$$$), and the maximum number of strings in the subtrees of $$$v_1$$$ and $$$v_2$$$ (let these be $$$b$$$ and $$$c$$$), and make updates of the form "add $$$dp_{v_1,b} \cdot dp_{v_2,c}$$$ to the value of $$$dp_{v, \min(a,b+c)}$$$". This dynamic programming will work in $$$O(2^n k^2)$$$ or $$$O(2^n k^3)$$$ depending on the implementation, which is too slow.
However, we can use the following optimizations to improve the complexity of the solution:
• all vertices on the same depth can be treated as equivalent, so we can actually calculate this dynamic programming not for $$$O(2^n)$$$ vertices, but just for $$$O(n)$$$;
• when handling transitions from some node's children to that node, let's split these transitions into two steps. The first step is iterating on the number of strings which fit into the subtrees of the children; the second step is iterating on the constraint for the subtree of the node. The first step is actually a convolution: if we don't consider the constraint for the node itself, then the transitions would be something like "add $$$dp_{v_1,b} \cdot dp_{v_2,c}$$$ to the value of $$$dp_{v, b+c)}$$$"; so it can be improved to $$$O(k \log k)$$$ with FFT. The second step can be improved to $$$O(k)$$$ as well, if we iterate on the minimum between the constraint for the node and the total number of strings which can be stored in the children, and maintain the sum on suffix for the values of dynamic programming.
Overall, these optimizations lead to a solution with complexity $$$O(n k \log k)$$$.