問題一覧 > 通常問題

No.1201 お菓子配り-4

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 65
作問者 : PCTprobabilityPCTprobability / テスター : hotmanwwhotmanww
15 ProblemId : 4783 / 出題時の順位表
問題文最終更新日: 2020-08-28 23:49:13

問題文

正整数 $N,M$ が与えられます。 この時長さが $N,M$ の整数列 $A_1,A_2,\ldots ,A_N$ と $B=B_1,B_2,\ldots ,B_M$ が与えられます。 数列 $B$ の最大値を $C$ とすると $C$ 人の子供がいます。 これらの子供には $1,2,\ldots ,C $ の番号がついています。 数列 $A,B$ からそれぞれ要素を選ぶ方法は $NM$ 通りありますが、その全てに対して以下の操作を行います。

選ばれた要素を $A_i,B_j$ とし、 $1$ から $B_j$ の番号がついている子供全員に対して $k$ の番号がついている子供には $2×\lfloor \frac{A_i×k}{B_j}\rfloor $ 個のお菓子をあげます。

この操作を全てする時にお菓子は最低で何個必要か出力してください。 ただし答えは非常に大きくなる可能性があるので $1000000007$ で割った余りを出力してください。

入力

$N$
$M$
$A_1\ A_2\ \dots\ A_N$
$B_1\ B_2\ \dots\ B_M$

  • 入力は全て整数である。
  • $1 \le N,M \le 2000=2×10^3$
  • $0 \le A_i\le 100000000=10^8$
  • $1 \le B_j\le 100000000=10^8$

出力

必要なお菓子の個数の最低値を $1000000007$ で割った余りを出力して最後に改行してください。

サンプル

サンプル1
入力
1
1
3
4
出力
12

  • $1$ 人目には $2×\lfloor \frac{3×1}{4}\rfloor=0 $ 個のお菓子を配ります。
  • $2$ 人目には $2×\lfloor \frac{3×2}{4}\rfloor=2 $ 個のお菓子を配ります。
  • $3$ 人目には $2×\lfloor \frac{3×3}{4}\rfloor=4 $ 個のお菓子を配ります。
  • $4$ 人目には $2×\lfloor \frac{3×4}{4}\rfloor=6 $ 個のお菓子を配ります。
計 $0+2+4+6=12$ 個のお菓子が必要です。

サンプル2
入力
6
9
234523 35645 223 3563 234 346
346 467568 234141 457 235235 4656 3452 457 2
出力
792159237

$1000000007$ で割った余りを出力してください。

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