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