No.990 N×Mマス計算(Kの倍数)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 89
作問者 : %20%20 / テスター : kotatsugamekotatsugame
17 ProblemId : 3907 / 出題時の順位表
問題文最終更新日: 2020-02-07 21:01:42

問題文

$N$ 行 $M$ 列からなるマス目があります。
上から $i$ 行目、左から $j$ 列目のマスを「マス $(i,j)$ 」とします。
マス $(i,1)$ の左には $A_i$ が、マス $(1,j)$ の上には $B_j$ が書かれています。

マス $(i,j)$ には、$A_i\ op\ B_j$ の計算結果を書き込みます。この値を $C_{i,j}$ とします。
ここで、$op$ は +* のどちらかです。
$op$ が + なら $C_{i,j}=A_i+B_j$ 、* なら $C_{i,j}=A_i\times B_j$ です。

$C_{i,j}$ が $K$ の倍数であるようなマス $(i,j)$ の個数を求めてください。

入力

$N$ $M$ $K$
$op$ $B_1$ $B_2$ $\cdots$ $B_M$
$A_1$
$A_2$
$\vdots$
$A_N$

入力は以下の制約を満たします。

  • $1\le N\le10^5$
  • $1\le M\le10^5$
  • $1\le K\le10^9$
  • $1\le A_i\le10^9$
  • $1\le B_j\le10^9$
  • $N,M,K,A_i,B_j$ は整数である
  • $op$ は +* のどちらかである

出力

$C_{i,j}$ が $K$ の倍数であるようなマス $(i,j)$ の個数を出力してください。

サンプル

サンプル1
入力
3 4 13
+ 5 12 6 13
8
27
3
出力
2

マス目には以下のように書き込むことになります。

$\begin{array}{c|c|} + & 5 & 12 & 6 & 13 \\\hline 8 & 13 & 20 & 14 & 21 \\\hline 27 & 32 & 39 & 33 & 40 \\\hline 3 & 8 & 15 & 9 & 16 \\\hline \end{array}$

サンプル2
入力
3 4 12
* 5 12 6 13
8
27
3
出力
4

マス目には以下のように書き込むことになります。

$\begin{array}{c|c|} * & 5 & 12 & 6 & 13 \\\hline 8 & 40 & 96 & 48 & 104 \\\hline 27 & 135 & 324 & 162 & 351 \\\hline 3 & 15 & 36 & 18 & 39 \\\hline \end{array}$

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