N-Dimensional Grid

爱被打了一巴掌 2022-03-19 15:26 165阅读 0赞

#

You are given an n-dimensional grid in which the dimensions of the grid are a1 × a2 × … × a**n. Each cell in the grid is represented as an n-tuple (x1, x2, …, x**n) (1 ≤ x**i ≤ a**i).

Two cells are considered to be adjacent if the Manhattan Distance between them is equal to 1. The Manhattan Distance between two cells X(x1, x2, …, x**n) and Y(y1, y2, …, y**n) is equal to: |x1 - y1| + |x2 - y2| + … + |x**n - y**n|.

Your task is to count how many pairs of cells are adjacents. Can you? Two pairs of cells are considered the same if they include the same cells, i.e the pair (c1, c2)is the same as (c2, c1).

Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the number of dimensions of the grid. Then a line follows containing n integers a1, …, a**n (1 ≤ a**i ≤ 105), in which a**i is the size of the i**th dimension.

The sum of n overall test cases does not exceed 6 × 106.

Output

For each test case, print a single line containing the number of pairs of adjacent cells modulo 109 + 7.

Example

Input

  1. 1
  2. 3
  3. 1 2 3

Output

  1. 7

Note

The absolute value |x| of a real number x is the non-negative value of x without regard to its sign. Namely, |x| = x for a positive x, |x| =  - x for a negative x (in which case  - x is positive), and |0| = 0. For example, the absolute value of 3 is 3, and the absolute value of  - 3 is also 3. The absolute value of a number may be thought of as its distance from zero.

题目:比赛时根本就没看这一题 比赛完看答案还是懵逼 被自己菜哭了 还摔了键盘,,

题目大意:有N维的空间(改成空间更好理解),给出每一维的大小,计算总的相邻点的个数

思维:代码篇幅中有写。

代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int w,n,a[100005];
  4. /*
  5. 本题的思路是 N维空间
  6. 第一维空间的时候 有sum=a[1]-1个相邻点
  7. 第二维空间的时候 有sum = sum*a[2] + a[1]*(a[2]-1) (低维的复制a[i]遍,然后是维维(低)之间的点数*低维一共有多少点)
  8. 。。。。
  9. */
  10. int main(){
  11. scanf("%d",&w);
  12. while(w--){
  13. scanf("%d",&n);
  14. for(int i=1;i<=n;i++)
  15. scanf("%d",&a[i]);
  16. long long sum=a[1]-1,num=a[1];
  17. for(int i=2;i<=n;i++){
  18. sum=sum*a[i];//对数复制(单位内的数量*第I维的size)
  19. sum%=1000000007;
  20. sum+=num*(a[i]-1);//维维之间的相邻点计算
  21. sum%=1000000007;
  22. num=num*a[i];
  23. num%=1000000007;
  24. }
  25. printf("%lld\n",sum);//注意在进行int的加减时会出现爆int的情况,wa两发,真菜!
  26. }
  27. return 0;
  28. }

发表评论

表情:
评论列表 (有 0 条评论,165人围观)

还没有评论,来说两句吧...

相关阅读

    相关 CSS Grid(1)

    > Grid 由水平线和垂直线构成 > 1、两条水平线中间的区域叫做轨道 > 2、两条垂直线中间的区域叫做列轨道 > 3、行列重叠出来的空间组成单元格 ![在这里

    相关 Grid网格布局

    简介 > Flex布局时一维的布局,即水平或垂直方向的布局。而Grid布局则划分成“行”和“列”,产生单元格,可以看作是二维的布局。Grid布局远比Flex布局强大

    相关 css grid 布局

    [css grid][] CSS Grid 网格布局 Grid 布局与 Flex 布局有一定的相似性,都可以指定容器内部多个项目的位置。但是,它们也存在重大区别。 F

    相关 Grid 布局

    这是一篇快速介绍网站未来布局的文章。 ![CSS Grid 布局][CSS Grid] Grid 布局是网站设计的基础,CSS Grid 是创建网格布局最强大和最简单的工具