問題一覧 > 通常問題

No.1731 Product of Subsequence

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

問題文

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

入力

N K
A1 A2 ⋯ AN

  • 1≤N≤2000
  • 1≤K≤109
  • 1≤Ai≤1018
  • 入力は全て整数である．

出力

積が K の倍数であるような空でない部分列の個数を 109+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

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

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