Multiset of Strings

题意翻译

定义二进制串为只包含 $01$ 的字符串。 给你 $n,k,f$，$1\le n\leq 15,1\le f,k\leq 2\times 10^5$，你需要给每个长度不超过 $n$ 的二进制串 $s$ 确定一个 $c_s\in [0,k]$ 的权值。然后你需要选出一个只包含长度**恰好**为 $n$ 的二进制串的**可重集合**，使得这个可重集合最大。并且满足对于所有长度**小于等于** $n$ 的二进制串 $s$，集合元素中，$s$ 作为集合中元素前缀的次数**不超过** $c_s$。 求安排 $c$ ，使得集合最大大小**恰好为 $f$** 的方案数，对 $998244353$ 取模。

题目描述

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 $ .

输入输出格式

输入格式

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 $ ).

输出格式

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 $ .

输入输出样例

输入样例 #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

说明

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\} $ .

**题目大意：**

题目定义了一个“二进制串”为只包含字符 '0' 和 '1' 的字符串。给定三个整数 $ n $, $ k $, 和 $ f $ （其中 $ 1 \le n \le 15 $, $ 1 \le k, f \le 2 \times 10^5 $），需要为每个长度不超过 $ n $ 的二进制串 $ s $ 分配一个权值 $ c_s $，这个权值是从 $ 0 $ 到 $ k $ 之间的整数。然后需要从所有长度恰好为 $ n $ 的二进制串中选出一个“可重集合”，使得这个集合尽可能大，同时满足对于所有长度小于等于 $ n $ 的二进制串 $ s $，在集合中，以 $ s $ 作为前缀的字符串数量不超过 $ c_s $。

目标是计算出一共有多少种分配 $ c_s $ 的方式，使得集合的最大大小恰好为 $ f $，并将这个数量对 $ 998244353 $ 取模。

**输入输出数据格式：**

- **输入格式：** 输入只有一行，包含三个整数 $ n $, $ k $, 和 $ f $。
- **输出格式：** 输出只有一行，包含一个整数，即满足条件的方案数对 $ 998244353 $ 取模后的结果。**题目大意：** 题目定义了一个“二进制串”为只包含字符 '0' 和 '1' 的字符串。给定三个整数 $ n $, $ k $, 和 $ f $ （其中 $ 1 \le n \le 15 $, $ 1 \le k, f \le 2 \times 10^5 $），需要为每个长度不超过 $ n $ 的二进制串 $ s $ 分配一个权值 $ c_s $，这个权值是从 $ 0 $ 到 $ k $ 之间的整数。然后需要从所有长度恰好为 $ n $ 的二进制串中选出一个“可重集合”，使得这个集合尽可能大，同时满足对于所有长度小于等于 $ n $ 的二进制串 $ s $，在集合中，以 $ s $ 作为前缀的字符串数量不超过 $ c_s $。 目标是计算出一共有多少种分配 $ c_s $ 的方式，使得集合的最大大小恰好为 $ f $，并将这个数量对 $ 998244353 $ 取模。 **输入输出数据格式：** - **输入格式：** 输入只有一行，包含三个整数 $ n $, $ k $, 和 $ f $。 - **输出格式：** 输出只有一行，包含一个整数，即满足条件的方案数对 $ 998244353 $ 取模后的结果。