「PHOI-1」斗之魂

Luogu

IDLGP9551

Time1000ms

Memory128MB

DifficultyP6

数学数论O2优化素数判断,质数,筛法快速数论变换 NTT

小 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 本身实力并没有因为人数的改变而改变，击败难度相对要简单一点，所以系统判定两人实际各获得 $k_{i,0}$ 块稀有金属，其中保证 $\dfrac{1}{k_{i,0}}=\dfrac{1}{k_{i,1}}+\dfrac{1}{k_{i,2}}$。小 X 已经计划好用第 $b_i$ 种方式击败第 $i$ 个 BOSS，但是考虑到某些因素，小 X 有 $q$ 次询问，每次询问给定一个正整数 $m$，为小 X 击败完所有 BOSS 后获得的稀有金属总数，已知 $k_{i,0},k_{i,1},k_{i,2}$ 均为正整数，求每次询问后所有可能的 $k$ 的值的方案数，两种方案不同当且仅当至少存在一个 $k$ 的值不同，由于这个答案可能很大，你只需要输出它对 $998244353$ 取模后的结果。 ## Input 第一行有两个整数 $n$ 和 $q$，分别表示 BOSS 个数和小 X 的询问次数。第二行有 $n$ 个正整数 $b_i$，表示小 X 用 $b_i$ 种方式击败第 $i$ 个 BOSS。接下来的 $q$ 行中每行有一个整数 $m$，为该次询问中小 X 击败完所有 BOSS 后获得的稀有金属总数。 ## Output 输出共 $q$ 行，第 $i$ 行输出一个答案为当小 X 击败完所有 BOSS 后获得的稀有金属总数为 $m$ 时，所有可能的 $k$ 的值的方案数并对它取模 $998244353$ 后的结果。 [samples] ## Background **本题数据已加强。** 小 X 忙了一天，于是打起了一款叫斗之魂的游戏。 ![](https://cdn.luogu.com.cn/upload/image_hosting/5ha5fx0q.png) ## Note **本题采用捆绑测试。** | Subtask | $n\le$ | $m \le$ | $q \le$ | 时限 | 分值 | | :-----: | :---------------: | :---------------: | :-----: | :----: | :--: | | $0$ | $10$ | $20$ | $5$ | $1s$ | $8$ | | $1$ | $30$ | $60$ | $5$ | $1s$ | $7$ | | $2$ | $40$ | $100$ | $10^3$ | $1s$ | $5$ | | $3$ | $150$ | $500$ | $10^3$ | $1s$ | $5$ | | $4$ | $200$ | $5000$ | $10^4$ | $1s$ | $20$ | | $5$ | $2000$ | $5 \times 10^4$ | $10^5$ | $1s$ | $25$ | | $6$ | $1.5 \times 10^5$ | $2.5 \times 10^5$ | $10^5$ | $1.8s$ | $30$ | 对于 $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$。 ### 样例解释 #1： - 当 $m=3$ 时，所有可能的 $k$ 的值的方案数为 $4$。第 $1$ 种：$k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=2$ 第 $2$ 种：$k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$ 第 $3$ 种：$k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$ 第 $4$ 种：$k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=1$ - 当 $m=4$ 时，所有可能的 $k$ 的值的方案数为 $7$。第 $1$ 种：$k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=3$ 第 $2$ 种：$k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=2$ 第 $3$ 种：$k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=2$ 第 $4$ 种：$k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=2$ 第 $5$ 种：$k_{1,0}=3,k_{1,1}=4,k_{1,2}=12,k_{2,0}=k_{2,1}=k_{2,2}=1$ 第 $6$ 种：$k_{1,0}=3,k_{1,1}=6,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$ 第 $7$ 种：$k_{1,0}=3,k_{1,1}=12,k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$

Samples

Input #1

Output #1

4
7

Input #2

Output #2

API Response (JSON)

{
  "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 本...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments