問題一覧 > 通常問題

No.1731 Product of Subsequence

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 122
作問者 : とりゐ / テスター : tko919
お気に入りにしたユーザー ProblemId : 6741 / 自分の提出
問題文最終更新日: 2021-11-05 21:46:27
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
yukicoder contest 321 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of $N$ positive integers. $A$ has $2^N-1$ non-empty subsequences. How many of them have a product of all elements that is a multiple of $K$? Print the count modulo $10^9+7$.

Input

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

  • $1\leq N\leq 2000$
  • $1\leq K\leq 10^{9}$
  • $1\leq A_i\leq 10^{18}$
  • All input values are integers.

Output

Print the number of non-empty subsequences whose product is a multiple of $K$, modulo $10^9+7$.

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
10 998244353
1 2 3 4 5 6 7 8 9 10
Output
0

Sample 4
Input
4 171654
141421356237 173205080756 223606797749 244948974278
Output
3

$A_i$ may not fit in a $32$ bit integer.

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