No.2578 Jewelry Store
Note
The PyPy3 implementation of the writer's intended solution runs in about 2,200 ms.
Problem Statement
There are $n$ gems, and the $i\ (1\leq i\leq n)$-th gem has beauty $A _ i$ and value $W _ i$. Both $A _ i$ and $W _ i$ are positive integers.
suisen makes a ring by choosing $1$ or more of the $n$ gems. suisen has a favorite positive integer $m$, and the value of the resulting ring is determined as follows.
- Suppose that the $i _ 1, i _ 2, \ldots, i _ k\ (1 \leq i _ 1 \lt i _ 2 \lt \cdots \lt i _ k \leq n)$-th gems are chosen.
- If $\mathrm{lcm}(A _ {i _ 1}, A _ {i _ 2}, \ldots, A _ {i _ k}) = m$, the value of the ring is $\displaystyle\prod _ {j = 1} ^ k W _ {i _ j}$.
- If $\mathrm{lcm}(A _ {i _ 1}, A _ {i _ 2}, \ldots, A _ {i _ k}) \neq m$, the value of the ring is $0$.
Find the sum of the values of all rings suisen can make, modulo $998244353$. More formally, find the following value.
$$ \left(\sum _ {k = 1} ^ n \sum _ {\overset{\scriptstyle 1 \leq i _ 1 \lt i _ 2 \lt \cdots \lt i _ k \leq n,}{\mathrm{lcm}(A _ {i _ 1}, A _ {i _ 2}, \ldots, A _ {i _ k}) = m}} \prod _ {j = 1} ^ k W _ {i _ j}\right) \bmod 998244353. $$
You are given $T$ test cases; solve the above problem for all of them. Note that the value of $m$ is common to the $T$ test cases.
Input
The input is given from Standard Input in the following format.
First, line $1$ contains the number of test cases $T$ and the positive integer $m$ common to the $T$ test cases.
$T\ m$
Each test case is given over $2$ lines in the following format. Note that $W$ is not given explicitly.
$n\ B\ C\ D$ $A _ 1\ A _ 2\ \cdots\ A _ n$
$W = (W _ 1, W _ 2, \ldots, W _ n)$ in this test case is defined as follows.
$$ W _ i = \begin{cases} B & \text{if }i=1, \newline C \cdot W _ {i - 1} + D & \text{if }i = 2, 3, \ldots, n. \end{cases} $$
- All input values are integers.
- $1\leq T\leq 1000$
- $1\leq n\leq 5\times 10 ^ 5$
- $1\leq m\leq 10 ^ {18}$
- $1\leq A _ i \leq 10 ^ {18}$
- $0\leq B,C,D \lt 998244353$
- The sum of $n$ over the $T$ test cases is at most $5\times 10 ^ 5$.
Note that the input may be very large.
Output
On the $i\ (1\leq i\leq T)$-th line, print the answer to the $i$-th test case. Print a newline after the answer to the last test case as well.
Sample
Sample 1
Input
3 20 6 1 1 1 1 5 2 4 7 10 1 1 2 3 1 20 141421356 173205080 22360679 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Output
640 0 747444483
This input consists of $3$ test cases, and $m=20$ in all of them.
-
Test case $1$: $n = 6$, $A = (1, 5, 2, 4, 7, 10),\ W = (1, 2, 3, 4, 5, 6)$. The values of rings are calculated as in the following examples.
- If the $1,2,3$-th gems are chosen: $\mathrm{lcm}(A _ 1, A _ 2, A _ 3)=10\neq m$, so the value of the ring in this case is $0$.
- If the $1,2,4$-th gems are chosen: $\mathrm{lcm}(A _ 1, A _ 2, A _ 4)=20=m$, so the value of the ring in this case is $W _ 1 \cdot W _ 2 \cdot W _ 4 = 8$.
The sum of the values of all possible rings is $640$, so print this value.
-
Test case $2$: $n = 1$, $A = (1),\ W = (1)$. There is no way to make a ring whose $\mathrm{lcm}$ is exactly $m$, so print $0$.
-
Test case $3$: Note that you need to print the sum of the values of the rings modulo $998244353$.
Sample 2
Input
1 1 1 1 1 1 1
Output
1
Note that a ring cannot be made without choosing even $1$ gem.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tko919