No.2313 Product of Subsequence (hard)
とりゐ
遭難者問題文最終更新日: 2023-05-24 21:33:13
問題文
長さ $N$ の正整数列 $A$ が与えられます．空でない $A$ の部分列は $2^N-1$ 個ありますが，そのうち全要素の積が $K$ の倍数であるようなものはいくつありますか．$998244353$ で割った余りを出力してください．
入力
$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}$
- 入力は全て整数である．
出力
積が $K$ の倍数であるような空でない部分列の個数を $998244353$ で割った余りを出力してください．
サンプル
サンプル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
入力
20 360 678 545 651 790 694 268 851 318 295 814 359 941 504 592 378 874 989 522 571 724
出力
855936
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。