No.2313 Product of Subsequence (hard)

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 :

とりゐ / テスター :

遭難者

1 ProblemId : 9665 / 自分の提出

問題文最終更新日: 2023-05-24 21:33:13

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

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

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

3 4
2 4 6

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

4 6
2 2 3 3

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

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

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