問題一覧 > 通常問題

No.2313 Product of Subsequence (hard)

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 21
作問者 : とりゐ / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 9665 / 自分の提出
問題文最終更新日: 2023-05-24 21:33:13
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

Problem Statement

You are given a sequence $A$ of positive integers of length $N$. There are $2^N-1$ non-empty subsequences of $A$. How many of them have a product of all elements that is a multiple of $K$? Output the answer modulo $998244353$.

Input

$N\ K$
$A_1\ A_2\ \cdots\ A_N$

  • $1\leq N\leq 3\times 10^5$
  • $1\leq K\leq 10^{9}$
  • $1\leq A_i\leq 10^{18}$
  • All inputs are integers.

Output

Output the number of non-empty subsequences whose product is a multiple of $K$, modulo $998244353$.

Sample

Sample 1
Input
3 4
2 4 6
Output
5

The non-empty subsequences whose product of all elements is a multiple of $4$ are the following $5$: $(4),(2,4),(2,6),(4,6),(2,4,6)$.

Sample 2
Input
4 6
2 2 3 3
Output
9

The non-empty subsequences whose product of all elements is a multiple of $6$ are: $4$ of $(2,3)$, $2$ of $(2,2,3)$, $2$ of $(2,3,3)$, and $1$ of $(2,2,3,3)$.

Sample 3
Input
20 360
678 545 651 790 694 268 851 318 295 814 359 941 504 592 378 874 989 522 571 724
Output
855936

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。