#D. 棋子分裂

    传统题 1000ms 256MiB

棋子分裂

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

有一个nn行的残缺棋盘,从上到下行号依次为11nn。第ii行有紧靠左边的连续aia_i个格子,且对于任意1i<n1\le i <n,有aiai+1a_i \ge a_{i+1}

例如,当n=3n=3,每行分别有3,2,23,2,2个格子时,棋盘如下所示:jIcMGT.png

现有一个棋子在左上角的格子里,其余格子均为空白。每次操作可以选择棋盘内的一个棋子,将其分裂成两个,其中一个往右移动一格,另一个往下移动一格。棋子可能会移动到棋盘外,一个格子里可以同时容纳任意多个棋子。

请你根据给定的棋盘,计算至少在多少次操作之后,棋盘内没有任何棋子。

【输入格式】

第一行一个整数tt,表示有tt组数据。

对于每组数据,第一行一个整数nn,表示棋盘的行数。

第二行nn个空格隔开的整数,表示每行的格子数量。

【输出格式】

tt行,每行一个整数,表示题目所求的操作次数,答案对109+710^9+7取余数。

2
2
3 2
3
3 2 2
6
10
1
10
15 14 12 10 8 7 6 4 0 0
3872

【样例解释】

样例1的第一组数据中:

第1次对(1,1)操作后,棋盘内的棋子为(2,1) (1,2)。

第2次对(2,1)操作后,棋盘内的棋子为(1,2) (2,2)。

第3次对(2,2)操作后,棋盘内的棋子为(1,2)。

第4次对(1,2)操作后,棋盘内的棋子为(1,3) (2,2)。

第5次对(2,2)操作后,棋盘内的棋子为(1,3)。

第6次对(1,3)操作后,棋盘内没有棋子。

【数据规模与约定】

对于20%20\%的数据,保证t=1,1n3,0ai3t=1, 1\le n\le 3, 0\le a_i\le 3

对于50%50\%的数据,保证t3t\le 3

对于100%100\%的数据,保证1t2000,1n1000,0ai10001\le t\le 2000,1\le n\le 1000, 0\le a_i\le 1000

CSP-J暑假集训(补考)

未参加
状态
已结束
规则
OI
题目
4
开始于
2021-8-20 14:00
结束于
2021-9-2 2:00
持续时间
300 小时
主持人
参赛人数
158