← 返回题目列表

Codeforces · 1709/F

F. 多组字符串

中文机器翻译题面 查看原题

给你三个整数 $$$n$$$、$$$k$$$ 和 $$$f$$$。

考虑长度从 $$$1$$$ 到 $$$n$$$ 的所有二进制字符串(即由字符 $$$0$$$ 和/或 $$$1$$$ 组成的所有字符串)。对于每个这样的字符串 $$$s$$$,您需要选择一个从 $$$0$$$ 到 $$$k$$$ 的整数 $$$c_s$$$。

如果对于长度从 $$$1$$$ 到 $$$n$$$ 的每个二进制字符串 $$$s$$$,多重集中以 $$$s$$$ 为其前缀的字符串数量不超过 $$$c_s$$$,则长度恰好为 $$$n$$$ 的二进制字符串多重集被认为是美丽的。

例如,设 $$$n = 2$$$、$$$c_{0} = 3$$$、$$$c_{00} = 1$$$、$$$c_{01} = 2$$$、$$$c_{1} = 1$$$、$$$c_{10} = 2$$$ 和 $$$c_{11} = 3$$$。字符串多重集 $$$\{11, 01, 00, 01\}$$$ 很漂亮,因为:

- 对于字符串 $$$0$$$,多重集中有 $$$3$$$ 字符串,其中 $$$0$$$ 是它们的前缀,$$$3 \le c_0$$$;
- 对于字符串$$$00$$$,多重集中有一个字符串,$$$00$$$ 是其前缀,$$$1 \le c_{00}$$$;
- 对于字符串 $$$01$$$,多重集中有 $$$2$$$ 字符串,其中 $$$01$$$ 是它们的前缀,$$$2 \le c_{01}$$$;
- 对于字符串 $$$1$$$,多重集中有一个字符串,$$$1$$$ 是其前缀,并且 $$$1 \le c_1$$$;
- 对于字符串 $$$10$$$,多重集中有 $$$0$$$ 字符串,其中 $$$10$$$ 是它们的前缀,$$$0 \le c_{10}$$$;
- 对于字符串 $$$11$$$,多重集中有一个字符串,$$$11$$$ 是其前缀,并且 $$$1 \le c_{11}$$$。

现在,针对问题本身。您必须计算为长度从 $$$1$$$ 到 $$$n$$$ 的每个二进制字符串 $$$s$$$ 选择整数 $$$c_s$$$ 的方法数量,使得美丽多重集的最大可能大小恰好为 $$$f$$$。

输入

输入的唯一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$f$$$ ($$$1 \le n \le 15$$$; $$$1 \le k, f \le 2 \cdot 10^5$$$)。

输出

打印一个整数 — 为每个长度从 $$$1$$$ 到 $$$n$$$ 的二进制字符串 $$$s$$$ 选择整数 $$$c_s$$$ 的方法数,使得美丽多重集的最大可能大小恰好为 $$$f$$$。因为它可能很大,所以打印它对 $$$998244353$$$ 取模。

示例

输入 #1

1 42 2

输出 #1

3

输入 #2

2 37 13

输出 #2

36871576

输入 #3

4 1252 325

输出 #3

861735572

输入#4

6 153 23699

输出#4

0

输入 #5

15 200000 198756

输出 #5

612404746

注意

在第一个示例中,选择整数 $$$c_s$$$ 的三种方法是:

- $$$c_0 = 0$$$, $$$c_1 = 2$$$, 则最大美丽多重集为$$$\{1, 1\}$$$;
- $$$c_0 = 1$$$, $$$c_1 = 1$$$, 则最大美丽多重集为$$$\{0, 1\}$$$;
- $$$c_0 = 2$$$, $$$c_1 = 0$$$,则最大美丽多重集为$$$\{0, 0\}$$$。