問題一覧 > 通常問題

No.2578 Jewelry Store

レベル : / AI推定難易度 : 2425 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : suisen / テスター : tko919
お気に入りにしたユーザー ProblemId : 9039 / 自分の提出
問題文最終更新日: 2023-12-01 01:16:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

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$.

    Here, for $k\ (\geq 1)$ positive integers $x _ 1, x _ 2, \ldots, x _ k$, we define $\mathrm{lcm}(x _ 1, x _ 2, \ldots, x _ k)$ as the smallest positive integer divisible by all of $x _ 1, x _ 2, \ldots, x _ k$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。