No.1349 Subset Product Queries
タグ : / 解いたユーザー数 42
作問者 :
KoD
/ テスター :
maguro
blackyuki
PCTprobability
注意
PyPy3 による AC は確認していますが、同じコードを Python 3 で提出したところ TLE しました。Python ユーザの方は、PyPy3 で提出されることを推奨します。
問題文
長さ $N$ の整数列 $A_1, A_2, \dots, A_N$ と正整数 $P$ ( $P$ は素数であるとは限りません ) 、さらに $Q$ 個のクエリが与えられます。
$i$ 個目のクエリでは、 $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ のうち一つ以上の要素を選んで、選んだ要素の総積を $P$ で割ったあまりが $K_i$ となるようにすることができるか判定してください。
入力
$N \,\, Q \,\, P$ $A_1 \,\, A_2 \,\, \ldots \,\, A_N$ $L_1 \,\, R_1 \,\, K_1$ $L_2 \,\, R_2 \,\, K_2$ $\vdots$ $L_Q \,\, R_Q \,\, K_Q$
- $1 \leq N \leq 5000$
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq P \leq 5000$
- $0 \leq A_i < P \,\, (1 \leq i \leq N)$
- $1 \leq L_i \leq R_i \leq N \,\, (1 \leq i \leq Q)$
- $0 \leq K_i < P \,\, (1 \leq i \leq Q)$
- 入力は全て整数
出力
全部で $Q$ 行出力してください。
$i$ 行目には、 $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ のうち一つ以上の要素を選んで、選んだ要素の総積を $P$ で割ったあまりが $K_i$ となるようにできるならば Yes と、できないならば No と出力してください。
サンプル
サンプル1
入力
5 2 7 3 1 4 1 5 1 5 5 2 4 3
出力
Yes No
$1$ 個目のクエリでは、例えば $A_1 \times A_2 \times A_3 \equiv 5 \,\, (\bmod 7)$ であるので、 Yes と出力します。
$2$ 個目のクエリでは、$A_2, A_3, A_4$ のみを用いて積を $7$ で割ったあまりが $3$ となるようにすることはできないので、 No と出力します。$A_1 \times A_4 \equiv 3 \,\, (\bmod 7)$ ですが、このクエリでは $A_1$ を使うことはできないことに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。