{"problem":{"name":"[蓝桥杯 2019 国 B] 燃烧权杖","description":{"content":"小 C 最近迷上了一款游戏。现在，在游戏中，小 C 有一个英雄，生命值为 $x$；敌人也有一个英雄，生命值为 $y$。除此以外，还有 $k$ 个士兵，生命值分别为 $a_1,a_2,\\cdots,a_k$。现在小 C 打算使用一个叫做“燃烧权杖”的技能。 “燃烧权杖”会每次等概率随机选择一个活着的角色（英雄或士兵），扣减其 $10$ 点生命值，然后如果该角色的生命值小于或等于 $0$，则该角色死","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8702"},"statements":[{"statement_type":"Markdown","content":"小 C 最近迷上了一款游戏。现在，在游戏中，小 C 有一个英雄，生命值为 $x$；敌人也有一个英雄，生命值为 $y$。除此以外，还有 $k$ 个士兵，生命值分别为 $a_1,a_2,\\cdots,a_k$。现在小 C 打算使用一个叫做“燃烧权杖”的技能。\n\n“燃烧权杖”会每次等概率随机选择一个活着的角色（英雄或士兵），扣减其 $10$ 点生命值，然后如果该角色的生命值小于或等于 $0$，则该角色死亡，不会再被“燃烧权杖”选中。“燃烧权杖”会重复做上述操作，直至任意一名英雄死亡。小 C 想知道使用“燃烧权杖”后敌方英雄死亡（即，小 C 的英雄存活）的概率。为了避免精度误差，你只需要输出答案模一个质数 $p$ 的结果，具体见输出格式。 \n\n## Input\n\n输入包含多组数据。\n\n输入第一行包含一个正整数 $T$，表示数据组数。\n\n接下来 $T$ 组，每组数据第一行包含四个非负整数 $x$、$y$、$p$、$k$，分别表示小 C 的英雄的生命值、敌方英雄的生命值，模数和士兵个数。\n\n第二行包含 $k$ 个正整数 $a_1,a_2,\\cdots,a_k$，分别表示每个士兵的生命值。 \n\n## Output\n\n对于每组数据，输出一行一个非负整数，表示答案模质数 p 的余数。\n可以证明，答案一定为有理数。设答案为 $a/b$（$a$ 和 $b$ 为互质的正整数），你输出的数为 $x$，则你需要保证 $a$ 与 $b\\times x$ 模 $p$ 同余；也即，$x \\equiv a\\times b^{-1} \\pmod p$，其中 $b^{-1}$ 表示 $b$ 模 $p$ 的逆元。\n\n[samples]\n\n## Note\n\n【样例说明】\n对于第一组数据，所求概率即为“燃烧权杖”第一次就扣减敌方英雄 $10$ 点生命值的概率，即 $1/2$。$2 \\times 51$ 模 $101$ 余 $1$。\n\n对于第二组数据，答案为 $1023/1024$，$1024 \\times 37$ 与 $1023$ 模 $101$ 同余。\n\n对于第三组数据，答案为 $99/128$。\n\n【评测用例规模与约定】\n\n对于 $10\\%$ 的评测用例，$x, y, a_1,\\cdots, a_k \\le 10$。\n\n对于 $20\\%$ 的评测用例，$x, y, a_1,\\cdots, a_k \\le 100$。\n\n对于 $50\\%$ 的评测用例，$x, y, a_1,\\cdots, a_k \\le 1000$。\n\n对于全部评测用例，$1\\leq T\\leq 100$，$1 ≤ x, y, a_1,\\cdots, a_k ≤ 10^9$，$3 \\le p \\le 10000$ 且 $p$ 为质数，$0 \\le k \\le 10$。\n\n蓝桥杯 2019 年国赛 B 组 J 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8702","tags":["2019","蓝桥杯国赛"],"sample_group":[["6\n1 10 101 0\n100 1 101 0\n50 30 4903 2\n1 1\n987 654 233 1\n321\n1000000000 999999999 233 3\n1 2 3\n1000000000 999999999 3 3\n1 2 3\n","51\n37\n1035\n118\n117\n2\n"]],"created_at":"2026-03-03 11:09:25"}}