P9551 「PHOI-1」Soul of Battle

**The testdata for this problem has been strengthened.** After a busy day, Little X started playing a game called Soul of Battle. 

Little X needs to defeat $n$ BOSSes. For the $i$-th BOSS, he can choose one of the following two ways: 1. Defeat the $i$-th BOSS alone and obtain $k_{i,0}$ pieces of rare metal, and it is guaranteed that $k_{i,0}=k_{i,1}=k_{i,2}$. 2. Defeat the $i$-th BOSS together with Little Y. Little X should obtain $k_{i,1}$ pieces of rare metal, and Little Y should obtain $k_{i,2}$ pieces of rare metal. However, the BOSS’s strength does not change with the number of players, and the fight becomes relatively easier, so the system determines that both players actually obtain $k_{i,0}$ pieces of rare metal. It is guaranteed that $\dfrac{1}{k_{i,0}}=\dfrac{1}{k_{i,1}}+\dfrac{1}{k_{i,2}}$. Little X has already planned to use method $b_i$ to defeat the $i$-th BOSS. However, due to some factors, Little X has $q$ queries. Each query gives a positive integer $m$, which is the total number of rare metals Little X obtains after defeating all BOSSes. It is known that $k_{i,0},k_{i,1},k_{i,2}$ are all positive integers. For each query, find the number of possible assignments of all $k$ values. Two assignments are considered different if and only if there exists at least one $k$ value that is different. Since the answer may be very large, output it modulo $998244353$.

The first line contains two integers $n$ and $q$, representing the number of BOSSes and the number of queries. The second line contains $n$ positive integers $b_i$, meaning that Little X uses method $b_i$ to defeat the $i$-th BOSS. Each of the next $q$ lines contains an integer $m$, the total number of rare metals Little X obtains after defeating all BOSSes in this query.

Output $q$ lines. The $i$-th line should be the number of possible assignments of all $k$ values when the total rare metals obtained by Little X after defeating all BOSSes is $m$, taken modulo $998244353$.

**This problem uses bundled tests.** # Constraints | Subtask | $n\le$ | $m \le$ | $q \le$ | Time Limit | Score | | :-----: | :---------------: | :---------------: | :-----: | :--------: | :---: | | $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$ | For $100\%$ of the data, it is guaranteed that $1 \le n \le 1.5 \times 10^5$, $1 \le m \le 2.5 \times 10^5$, $1 \le b_i \le 2$, and $1 \le q \le 10^5$. ### Sample Explanation #1: - When $m=3$, the number of possible assignments of all $k$ values is $4$. Type $1$: $k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=2$ Type $2$: $k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$ Type $3$: $k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$ Type $4$: $k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=1$ - When $m=4$, the number of possible assignments of all $k$ values is $7$. Type $1$: $k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=3$ Type $2$: $k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=2$ Type $3$: $k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=2$ Type $4$: $k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=2$ Type $5$: $k_{1,0}=3,k_{1,1}=4,k_{1,2}=12,k_{2,0}=k_{2,1}=k_{2,2}=1$ Type $6$: $k_{1,0}=3,k_{1,1}=6,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$ Type $7$: $k_{1,0}=3,k_{1,1}=12,k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$ Translated by ChatGPT 5