← 返回题目列表

AtCoder · wupc2019_h

H. Doki Doki 编程俱乐部!

中文机器翻译题面 查看原题

配点 : \(200\) 点

問題文

在W大学,俱乐部活动活跃,设有竞技项目。 圆圈 \(i\ (0 \leq i \leq N-1)\) 为 \(K_i\),\(j\ (0 \leq j \leq K_i-1)\) 成员的比例为 \(A_{i,j}\)。

每天,我们都在争论哪个圈子用电脑房,圈子们通过一场编程竞赛来决定。 比赛是每个圈子成员之间的一对一对决,但成员较少的俱乐部轮流进行比赛,成员人数与较大组的人数相匹配。

圆圈 \(X\) 和 \(Y\) 之间竞争的“白炽强度”表示为参赛成员评分的乘积之和。 用公式来说,它看起来是这样的。 对于序列

  • ,对于 \(A_X,A_Y\),\(\sum{((A_{X,\ {j \mod K_X} \times A_{Y,\ {j \mod K_Y}}}\) 在 \(0 \leq j \leq j \leq \max(K_X,K_Y)-1\)

现在,对峙正在发生 \(Q\),第一次对峙是在圆圈 \(X_i\) 和圆圈 \(Y_i\) 之间。 每个对局都瞄准“热度”。 然而,由于答案可能很大,请回答“除以 \(10^9+7\” 后的多余值)。

制約

  • \(2 \leq N \leq 200000\)
  • \(1 \leq K_i\)
  • \(\sum K_i \leq 200000\)
  • \(1 \leq A_{i,j} \leq 10^9\)
  • \(1 \leq Q \leq 200000\)
  • \(0 \leq X_i, Y_i \leq N-1\)
  • \(X_i \neq Y_i\)
  • 所有输入值都是整数。 如果您想走

入力

输入是按以下格式从标准输入给出的。

\(N\)
\(K_0\ A_{0,0}\ A_{0,1}\ \dots\ A_{0,K_0-1}\)
\(K_1\ A_{1,0}\ A_{1,1}\ \dots\ A_{1,K_1-1}\)
\(\vdots\)
\(K_{N-1}\ A_{{N-1},0}\ A_{{N-1},1}\ \dots\ A_{{N-1},K_{N-1}-1}\)
\(Q\)
\(X_0\ Y_0\)
\(X_1\ Y_1\)
\(\vdots\)
\(X_{Q-1}\ Y_{Q-1}\)

出力

对于每个查询,请输出答案除以 \(10^9+7\) 的余数。


入力例 1

3
1 7
2 5 6
3 3 3 4
3
0 1
0 2
1 2

出力例 1

77
70
53

例如,对于第二个查询,关注数列 \(A_0,A_2\),由 \(K_0=1,K_2=3\) 可得答案为 \(A_{0,0} \times A_{2,0}+A_{0,0} \times A_{2,1}+A_{0,0} \times A_{2,2}=70\)。

对于第三个查询,注意数列\(A_1,A_2\),由\(K_1=2,K_2=3\)可得答案为\(A_{1,0} \times A_{2,0}+A_{1,1} \times A_{2,1}+A_{1,0} \times A_{2,2}=53\)。


入力例 2

2
3 1000000000 999999999 999999998
10 1 2 3 4 5 6 7 8 9 10
1
0 1

出力例 2

999999571

\(10^9+7\) 以输出“do”(除法)。