题目描述

在一个物理法则与我们的宇宙不同的宇宙, 能量在能量环上会按照如下的方式传递:

如果在环上的i点处具有能量$A_i$, 那么在下一秒对于环上向任一方向走$D_i$处的能量会增加$A_i*B_{D_i}$

(注意, 能量传递后该位置原有的能量也不会丢失)

你可以认为能量的传递是瞬时的, 至于能量为什么会变多...因为zdw太懒了随手糊的题面(跑)

给定当前环上的能量信息与传递关系, 求t秒后每个点的能量值

由于答案和输出文件过大, 这里使用压缩的方式来输出答案:

假设原答案(也就是输出)为数组${A_i}$, 则你应按如下方式计算实际输出的答案:

int getans(int A[],int n){
    long long res=0;
    for(int i=0;i<n;++i)
        //printf("%d ",A[i]);
        res=(res*233+A[i]+19260817)%1000000007;
   return res;
}

题意解释:对于能量环{2,0,0,0,0,0,0,0,0}, 如果传递关系为{0,1}

那么下一秒的状态为{2,0,2,0,0,0,0,2,0}

再下一秒的状态为{6,0,4,0,2,2,0,4,0}

再下一秒的状态为{14,0,12,2,6,6,2,12,0}

输入描述

第一行一三个整数n,m,T表示环的大小, 能量传递的最远距离和询问次数

接下来一行n个整数 $A_i$ 表示在环上i点处的初始能量

接下来一行m个整数 $B_i$ 表示距离为i处传递能量的份数

接下来T行每行一个整数 $Q_i$ 询问 $Q_i$秒后的能量环的状态

输出描述

对于每组询问, 输出一行一个整数表示答案

样例输入：

3 3 4
1 1 2
6 5 2
1
2
3
233

样例输出：

159589809
209860057
592344986
388422764

样例解释

第一秒后状态为 $[1,1,2] + [1 * (2 + 2),1 * (6 + 5),1 * (5 + 6)] + [1 * (5 + 6),1 * (2 + 2),1 * (6 + 5)] + [2 * (5 + 6),2 * (6 + 5),2 * (2 + 2)]$

也就是 $[1,1,2] + [4,11,11] + [11,4,11] + [22,22,8] =[38,38,32] $.

$ ( ( ( 38 + 19260817 ) * 233 +38 +19260817 ) * 233 + 32 + 19260817 ) Mod\ 1000000007 = 159589809 $

数据范围

保证 $ 0 < T <= 300000, 1 <= A_i,B_i <= 10^{9}， 1 <= Q_i <= 10^{18}, 1 < n <=10, m<=100 $

子任务1:(40分)

保证 $ 0 < T <= 10000, 1 <= Q_i <= 10^9, n <= 3 $

子任务2:(100分)

保证 $ 0 < T <= 100000, n <= 3 $

子任务3:(200分)

无其他限制

题目来源

zdw1999