問題一覧 > 通常問題

No.1731 Product of Subsequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 : とりゐとりゐ / テスター : tko919tko919
7 ProblemId : 6741 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-05 21:46:27

問題文

長さ $N$ の正整数列 $A$ が与えられます．空でない $A$ の部分列は $2^N-1$ 個ありますが，そのうち全要素の積が $K$ の倍数であるようなものはいくつありますか．$10^9+7$ で割った余りを出力してください．

入力

$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}$
  • 入力は全て整数である．

出力

積が $K$ の倍数であるような空でない部分列の個数を $10^9+7$ で割った余りを出力してください．

サンプル

サンプル1
入力
3 4
2 4 6
出力
5

全要素の積が $4$ の倍数であるような空でない部分列は $(4),(2,4),(2,6),(4,6),(2,4,6)$ の $5$ つです．

サンプル2
入力
4 6
2 2 3 3
出力
9

全要素の積が $6$ の倍数であるような空でない部分列は $(2,3)$ が $4$ つ，$(2,2,3)$ が $2$ つ，$(2,3,3)$ が $2$ つ，$(2,2,3,3)$ が $1$ つです．

サンプル3
入力
10 998244353
1 2 3 4 5 6 7 8 9 10
出力
0

サンプル4
入力
4 171654
141421356237 173205080756 223606797749 244948974278
出力
3

$A_i$ は $32$ bit整数に収まらないことがあります．

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