{"problem":{"name":"「PHOI-1」斗之魂","description":{"content":"小 X 要击败 $n$ 个 BOSS，他可以选择以下两种击败 BOSS 的方式： 1. 独自一人击败第 $i$ 个 BOSS 并获得 $k_{i,0}$ 块稀有金属，且保证 $k_{i,0}=k_{i,1}=k_{i,2}$。 2. 和小 Y 一起击败第 $i$ 个 BOSS ，小 X 理应获得 $k_{i,1}$ 块稀有金属，小 Y 理应获得 $k_{i,2}$ 块稀有金属，但是 BOSS 本","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":"LGP9551"},"statements":[{"statement_type":"Markdown","content":"小 X 要击败 $n$ 个 BOSS，他可以选择以下两种击败 BOSS 的方式：\n\n1. 独自一人击败第 $i$ 个 BOSS 并获得 $k_{i,0}$ 块稀有金属，且保证 $k_{i,0}=k_{i,1}=k_{i,2}$。\n2. 和小 Y 一起击败第 $i$ 个 BOSS ，小 X 理应获得 $k_{i,1}$ 块稀有金属，小 Y 理应获得 $k_{i,2}$ 块稀有金属，但是 BOSS 本身实力并没有因为人数的改变而改变，击败难度相对要简单一点，所以系统判定两人实际各获得 $k_{i,0}$ 块稀有金属，其中保证 $\\dfrac{1}{k_{i,0}}=\\dfrac{1}{k_{i,1}}+\\dfrac{1}{k_{i,2}}$。\n\n小 X 已经计划好用第 $b_i$ 种方式击败第 $i$ 个 BOSS，但是考虑到某些因素，小 X 有 $q$ 次询问，每次询问给定一个正整数 $m$，为小 X 击败完所有 BOSS 后获得的稀有金属总数，已知 $k_{i,0},k_{i,1},k_{i,2}$ 均为正整数，求每次询问后所有可能的 $k$ 的值的方案数，两种方案不同当且仅当至少存在一个 $k$ 的值不同，由于这个答案可能很大，你只需要输出它对 $998244353$ 取模后的结果。\n\n## Input\n\n第一行有两个整数 $n$ 和 $q$，分别表示 BOSS 个数和小 X 的询问次数。\n\n第二行有 $n$ 个正整数 $b_i$，表示小 X 用 $b_i$ 种方式击败第 $i$ 个 BOSS。\n\n接下来的 $q$ 行中每行有一个整数 $m$，为该次询问中小 X 击败完所有 BOSS 后获得的稀有金属总数。\n\n## Output\n\n输出共 $q$ 行，第 $i$ 行输出一个答案为当小 X 击败完所有 BOSS 后获得的稀有金属总数为 $m$ 时，所有可能的 $k$ 的值的方案数并对它取模 $998244353$ 后的结果。\n\n[samples]\n\n## Background\n\n**本题数据已加强。**\n\n小 X 忙了一天，于是打起了一款叫斗之魂的游戏。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5ha5fx0q.png)\n\n## Note\n\n**本题采用捆绑测试。**\n\n| Subtask |      $n\\le$       |      $m \\le$      | $q \\le$ |  时限  | 分值 |\n| :-----: | :---------------: | :---------------: | :-----: | :----: | :--: |\n|   $0$   |       $10$        |       $20$        |   $5$   |  $1s$  | $8$  |\n|   $1$   |       $30$        |       $60$        |   $5$   |  $1s$  | $7$  |\n|   $2$   |       $40$        |       $100$       | $10^3$  |  $1s$  | $5$  |\n|   $3$   |       $150$       |       $500$       | $10^3$  |  $1s$  | $5$  |\n|   $4$   |       $200$       |      $5000$       | $10^4$  |  $1s$  | $20$ |\n|   $5$   |      $2000$       |  $5 \\times 10^4$  | $10^5$  |  $1s$  | $25$ |\n|   $6$   | $1.5 \\times 10^5$ | $2.5 \\times 10^5$ | $10^5$  | $1.8s$ | $30$ |\n\n对于 $100\\%$ 的数据，保证 $1 \\le n \\le 1.5 \\times 10^5$，$1 \\le m \\le 2.5 \\times 10^5$，$1 \\le b_i \\le 2$，$1 \\le q \\le 10^5$。\n\n### 样例解释 #1：\n\n- 当 $m=3$ 时，所有可能的 $k$ 的值的方案数为 $4$。\n\n    第 $1$ 种：$k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=2$\n\n    第 $2$ 种：$k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$\n\n    第 $3$ 种：$k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$\n\n    第 $4$ 种：$k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=1$\n\n- 当 $m=4$ 时，所有可能的 $k$ 的值的方案数为 $7$。\n\n    第 $1$ 种：$k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=3$\n\n    第 $2$ 种：$k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=2$\n\n    第 $3$ 种：$k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=2$\n\n    第 $4$ 种：$k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=2$\n\n    第 $5$ 种：$k_{1,0}=3,k_{1,1}=4,k_{1,2}=12,k_{2,0}=k_{2,1}=k_{2,2}=1$\n\n    第 $6$ 种：$k_{1,0}=3,k_{1,1}=6,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$\n\n    第 $7$ 种：$k_{1,0}=3,k_{1,1}=12,k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9551","tags":["数学","数论","O2优化","素数判断,质数,筛法","快速数论变换 NTT"],"sample_group":[["2 2\n2 1\n3\n4\n","4\n7\n"],["5 5\n1 2 1 2 1\n4\n6\n8\n10\n12\n","0\n9\n119\n630\n2210"]],"created_at":"2026-03-03 11:09:25"}}