[THUPC 2023 决赛] 老虎机

小 I 经营着一个电玩城，最近引进的新型老虎机深受欢迎。 作为经营者，小 I 首先需要设定老虎机的状态。老虎机的状态为一个三元组 $(l,S,\mathbf{p})$，其中 - $l$ 是一个正整数； - $S$ 是一个非空字符串集合，其中所有的字符串均是长度为 $l$ 的 01 串； - $\mathbf{p}$ 是一个长度为 $l$ 的实数序列 $p_0,p_1,\dots,p_{l-1}$，其中对于任意 $0 \le i \le l - 1$，$0 < p_i \le 1$。 设定好状态后即可开始游戏。每一轮游戏的流程如下： - 玩家首先获得老虎机的状态 $(l,S,\mathbf{p})$。 - 老虎机内部选择一个串 $s \in S$ 作为答案串，玩家需要通过与老虎机进行若干次交互得到答案串。 - 每一次交互中，玩家投入一个游戏币并拉下老虎机的拉杆，然后老虎机的界面中会出现一个长度为 $l$ 的信息串 $t$。对于 $0 \le i \le l - 1$，$t_i$ 有 $p_i$ 的概率为 $s_i$，有 $(1-p_i)$ 的概率为 `?`。 - 交互过程中生成信息串进行的所有随机过程两两独立。 - 当玩家可以根据**老虎机的状态和交互得到的若干信息串**唯一确定答案串后，即可将答案串输入老虎机并结束游戏、获得奖励。 小 I 设定好了一个状态，但还不知道设定多少奖励。为了让奖励和难度匹配，小 I 想知道：对于 $S$ 中的每个串 $t$，在玩家以最优策略游玩（即一旦可以唯一确定答案串就结束游戏）的情况下，若答案串为 $t$，玩家期望需要投入多少游戏币。 由于小 I 不喜欢实数，你需要将答案对 $998244353$ 取模。 ## Input **本题有多组测试数据。** 第一行一个整数 $T$ 表示测试数据组数，接下来依次输入每组测试数据。 对于每组测试数据， - 第一行两个整数 $l,n$，表示字符串长度和 $S$ 的大小。 - 第二行 $l$ 个整数 $c_0,c_1,\dots,c_{l-1}$，其中 $p_i = \frac{c_i}{10^4}$。 - 接下来 $n$ 行，第 $i$ 行一个长度为 $l$ 的 01 串 $s_i$，描述 $S$ 中的一个字符串。 ## Output 对于每组测试数据输出 $n$ 行，第 $i$ 行表示答案串为 $s_i$ 时，在最优策略下玩家期望投入多少游戏币，对 $998244353$ 取模，题目保证这个值总是在模意义下存在。 [samples] ## Note **【样例解释 #1】** - 对于第一组测试数据，每一次交互有 $\frac{5000}{10000} = \frac{1}{2}$ 的概率知道答案串是 $0$ 还是 $1$，有 $\frac{1}{2}$ 的概率不能获得信息，因此期望游戏币数为 $\sum_{i=1}^{+\infty} \frac{i}{2^i} = 2$。 - 对于第二组测试数据，每一次交互都可以得到字符串的第二位，有 $\frac{1}{10000}$ 的概率得到字符串的第一位。第二个字符串为答案串时可以通过字符串的第二位唯一确定，而其他两个字符串为答案串时必须要得到字符串的第一位。 - 对于第三组测试数据，由于 $|S| = 1$，所以不需要任何交互就可以确定答案串。 - 对于第四组测试数据，我有一个绝妙的解释，可这里空间太小写不下。 **【数据范围】** 对于所有测试数据，$1 \le T \le 10$，$1 \le l \le 15$，$1 \le n \le 2^l$，$1 \le c_i \le 10^4$，$s_1,\dots,s_n$ 为两两不同的长度为 $l$ 的 01 串。 **【后记】** “喂喂喂，未成年人不准进入电玩城！什么？你们说你们要进去学算法竞赛？谁信你的鬼话！” **【题目来源】** 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。 题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。