「个人赛」2021年广东工业大学第十五届文远知行杯程序设计竞赛

A M形字符

题意：

M形字符串指的是由两个相同的回文串拼接而成

给你一个串S，问有多少个前缀是M形字符串

思路：

M形是有两个相同的回文串构成的，所以这个M形串本身就是回文串，我们只需要判断一个串是回文串的同时，他的一半也是回文串即可

那如何判是不是回文串呢，这里我们使用哈希进行判断

如果一个串的正序哈希值等于其逆序哈希，则说明这个串是回文串

哈希的计算方法：

pre[i] = pre[i - 1] * seed + s[i] - 'a' + 1;

对于中间取的一段的哈希值，我们可以利用类似于差分的方法

pre[r] - pre[l - 1] * base[r - l + 1];

乘base[r – l + 1]是为了将其化为“同阶”

AC码：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1500000 + 7
#define endl '\n'
#define seed 1331
const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int pre[MAX], back[MAX], base[MAX];
string s;
ll   len;

int idx(char x){
    return (int)(x - 'a' + 1);
}

int getpre(int l, int r){//获得区间[l, r]的顺序哈希值
    return pre[r] - pre[l - 1] * base[r - l + 1];
}

int getback(int l, int r){//获得区间[l, r]的逆序哈希值
    return back[r] - back[l - 1] * base[r - l + 1];
}

bool judge(int i, int j){//判断正逆序的哈希是否相同
    return getpre(i, j) == getback(len - j + 1, len - i + 1);
}

int half(int x){
    return (x + 1) / 2;
}

int main(){
    cin>>s;
    s = " " + s;
    len = s.size();
    base[0] = 1;
    for(int i = 1; i <= len; ++i){
        base[i] = base[i - 1] * seed;
        pre[i] = (pre[i - 1] * seed + idx(s[i]));
        back[i] = (back[i - 1] * seed + idx(s[len - i + 1]));
    }
    int ans = 0;
    for(int i = 1; i <= len; ++i){
      //如果这个串是回文串，且他的一半也是回文串，就更新答案
        if(judge(1, i) && judge(1, half(i)))ans++;
    }
    cout<<ans<<endl;
    return 0;
}

在求正逆序哈希的时候，我将base[r – l + 1]换成pow(seed, r – l + 1)再理论方法来说是没有问题的，调了好长时间这个数还是对不上(╥﹏╥)

B找山坡

题意：

母牛哥在电脑面前坐久了，想站起来看看窗外的小山坡，于是就想出了这个问题：给定一个大小为n的数组a，序号从1开始，计算:

max{ R – L | 1 <= L <= R <= n, a[L] == a[R], 对于所有i (L <= i <= R), 满足a[i] >= a[L] }. 也就是找到两个坐标,这两个坐标的值相等,并且他们之间的值都大于等于这两个坐标上的值. 这两个坐标相减最大能是多少.

思路：

可以用线段数来做，也可以用单调栈来做

先说结论：

栈存下标

如果tr[i] 小于栈顶对应的元素，就将栈顶元素扔出去（这个时候我们可以知道，被扔出去的元素肯定是在tr[i]之前的，他的值大于tr[i]，就不符合我们要求的两边的值大于内部的值，也就不会对结果产生贡献）

如果tr[i] 等于栈顶对应的元素，就更新答案

其他情况就把tr[i]对应的下标塞进去

注意如果要取栈顶一定要判栈是否为空

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define endl '\n'
#define seed 1331
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//const ll mod = 1e9 + 7;
//#define mod 571373;
//#define mod 1000000007
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x, ans;
int tr[MAX];

stack<int>st;

int main(){
    cin>>n;
    for(int i = 1; i <= n; ++i)cin>>tr[i];
    for(int i = 1; i <= n; ++i){
        while (!st.empty() && tr[i] < tr[st.top()]) {
            st.pop();
        }
        if(!st.empty() && tr[i] == tr[st.top()])ans = max(ans, i - st.top());
        else st.push(i);
    }
    cout<<ans<<endl;
    return 0;
}

C 涂墙

题意：

母牛哥有一桶油漆,把它用完可以给n平方米的墙涂上颜色. 母牛哥想要在墙上涂5个正方形(这些正方形的边长都是整数,单位是米),并且刚好把油漆用完. 母牛哥能做到吗?

思路1：找规律

0 1 2 3 4 6 7 9 10 12 15 18 33 这些数无法由五个平方数构成，其他都可以滴

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, m, ans;
int tr[1005];

int main(){
    cin>>t;
    while (t--) {
        cin>>n;
        if(n == 1|| n == 0 || n == 2 ||  n == 3 || n == 4 || n == 6 || n == 7 || n == 9 || n == 10 || n == 12 || n == 15 || n == 18 || n == 33)cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}

//dfs暴力
//void dfs(int x, int num){
//    if(x == n && num == 5){
//        ans = 1;
//        return;
//    }
//    else if(num == 5 && x != n)return;
//    for(int i = 1; i <= 30; ++i){
//        dfs(x + tr[i], num + 1);
//    }
//
//}
//
//int main(){
//    t = IntRead();
//    int len = 0;
//    for(int i = 1;i <= 1000; ++i)tr[++len] = i * i;
////    n = 55;
////    dfs(0, 0);
////    cout<<ans<<endl;
//    for(int i = 1; i <= t; ++i){
//        n = i;
//        ans = 0;
//        dfs(0, 0);
//        if(ans == 1)cout<<i<<' '<<"YES\n";
//        else cout<<i<<' '<<"NO\n";
//    }
//    return 0;
//    while (t--) {
//        n = IntRead();
//        dfs(0, 0);
//        if(ans == 1)cout<<"YES\n";
//        else cout<<"NO\n";
//    }
//}

思路2:优美的暴力

看了大佬们的代码才发现，大佬口中的暴力和我的暴力并不相同

就像人与人的悲欢并不相通，呜呜呜(╥﹏╥)

dfs的时候尽量从大的开始找，不要从小的一直找，因为你小的可能找了五个才发现不行，才开始回退，对于类似于1这种的，就会搜的特别多，而你找大的，可能一下子就超了，就开始换下一个，就不会太暴力，这就是这个题的暴力美学orz

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 1331
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//const ll mod = 1e9 + 7;
//#define mod 571373;
//#define mod 1000000007
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n;

bool dfs(int n, int k){//n代表数，k代表已经凑几个数了
    if(n == 0 && k == 0)return true;
    if(n <= 0 || k == 0)return false;
    else{
        for(int i = sqrt(n); i; --i){//从大数开始找
            if(dfs(n - i * i, k - 1))
                return true;
        }
    }
    return false;
}

int main(){
    cin>>t;
    while (t--) {
        cin>>n;
        if(dfs(n, 5))cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

D动态序列

题目描述：

给出n（1 <= n <= 100000）个整数 ai（1 <= ai <= 1000000000）的序列，有q（1 <= q <= 100000）个询问，设序列长度为len，序号从1开始，每个询问有如下操作：

1 b：序列中所有数乘以整数b（1 <= b <= 1000000000）

2 b：序列中所有数增加整数b（1 <= b <= 1000000000）

3 b：在序列头部添加一个整数b（1 <= b <= 1000000000）

4 b：在序列尾部添加一个整数b（1 <= b <= 1000000000）

5 p：输出序列的第p（1 <= p <= len）个数，并将结果对1000000007取模

题目保证所有操作都是合法的！

思路：

对于每一个需要输出的数，都是经过多次乘法和加法的，我们就可以写作 $mul * a + add$ 的形式，所以我们可以只需要更新记录mul 和add即可（mul为乘的数，初始为1，add为加的数，初始为0）

对于操作1 : 我们取其中一个数tr[i]来看
$即$ $也就是$

还是一个数乘以 a 加上一个数的形式我们需要更新mul 和 add 的值

对于操作2 同理，我们只需要跟新add的值即可

要注意，我们输出的时候是输出 $mul * tr[i] + add$ ，所以对于新加入的元素p，他想要进入这个数组，就必须转换成 $mul * x + add$ 的形式，也即是将 x 加入数组，此时

因为这题是需要取模的，所以就不能使用除法，得使用逆元来求x

对于本题，模是1e7是质数，所以我们可以使出秘技：费马小定理来求逆元，也就是 x = (p – add) * quick_pow(mul, mod – 2)

因为3是向头部加元素，数据最多1e5，所以就把1e5 + 1 当作是数组的头，1e5 + n 当作是数组的尾，注意要开大点数组，取模的时候你就遇到计算就取一步模

记得初始化mul 和 add

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 300000 + 50
#define endl '\n'
#define seed 1331
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
//#define mod 1000000007
typedef  long long ll ;
const ll mod = 1e9 + 7;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, m, a, b, sta, en, mul, add, x;
ll tr[MAX];

ll quick_pow(ll a, ll b){//快速幂
    ll ans = 1;
    a %= mod;
    while (b) {
        if(b & 1){
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

void solve(ll a, ll b){
    switch (a) {
        case 1:
            mul = (mul * b) % mod;
            add = (add * b) % mod;
            break;
        case 2:
            add = (add + b) % mod;
            break;
        case 3:
            x = (((b - add + mod) % mod) * (quick_pow(mul, mod - 2) % mod)) % mod;
            tr[--sta] = x;
            break;
        case 4:
            x = (((b - add + mod) % mod) * (quick_pow(mul, mod - 2) % mod)) % mod;
            tr[++en] = x;
            break;
        case 5:
            cout<<((mul * tr[sta + b - 1]) % mod + add % mod) % mod<<endl;
            break;
    }
}

int main(){
    cin>>n>>m;
    sta = 1e5 + 1;en = 1e5 + n;
    for(ll i = sta; i <= en; ++i)cin>>tr[i];
    mul = 1;add = 0;
    while (m--) {
        cin>>a>>b;
        solve(a, b);
    }
    return 0;
}

E 捡贝壳

题意：

给你n个贝壳，每个贝壳有不同的质量，进行q次询问，询问的是区间[l, r]中的贝壳质量是x的倍数的有多少个

思路1：

一开始最暴力的方法是用个二维数组存因子的前缀和，然后就可以做差直接查询，但是空间不允许，就得放弃

所以，我们就可以采取分块的方法，将n个贝壳进行分块，每一块的大小不超过 $\sqrt n$ ，然后像线段树求区间和一样一段段的求即可

分块操作：我这里选择的是输入的时候就直接分块，你也可以像其他人那样写个函数，等输入完了再分

分块的时候最好是从0这个数开始，比如0 1 2 3 4 5 6 7 8，块是3，前三个数除以3刚好是0，但如果你从1开始计数，那就不方便了

for(int i = 1; i <= n; ++i){
        ar[i] = IntRead();//快读
        for(int j = 1; j * j <= ar[i]; ++j){//质因数分解
            if(ar[i] % j == 0){//判断能否整除j
                tr[(i - 1) / cnt + 1][j]++;//能整出就对该块的j进行++操作，这里从1输入，所以对i-1进行判块，且我这里cnt从1开始是为了后面的操作做准备，一会讲
                if(ar[i] / j != j)tr[(i - 1) / cnt + 1][ar[i] / j]++;//对于j这个因子，肯定有ar[i] / j这另一个因子，但需要判断这两个因子是不是相同的，也就是ar[i]找个数可能是平方数，那他开平方的数就只需要计算一遍
            }
        }
    }

求解：

分两种情况：

l 和 r 在一个块里面，这时候就直接打个暴力，从 l 循环到 r，最多最多也就跑300多，因为分的块最大也就是 $\sqrt 100000$
l 和 r 不在一个块里面，这个时候就分三部分进行运算

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hfDTJ9mv-1617196473580)(/Users/chelsea/Library/Application Support/typora-user-images/image-20210330111019462.png)]

见图：由l 到 a块的结束 + a块与b块中间的块 + b块的开始到 r

int getnum(int l, int r, int x){
  //判断l和r在哪个块里面，注意这里要让块的值是大于等于1的，所以就得加一，因为如果第一个块等于0，那0乘以块的大小还是0，我们就无法得到一个块的尾部
    int a = l / cnt + 1, b = r / cnt + 1;
    int sum = 0;
    if(a == b){//判断在同一个块内
        for(int i = l; i <= r; ++i){
            if(ar[i] % x == 0)sum++;//直接莽暴力
        }
        return sum;
    }
  //第一部分： 从l 开始，到 a块的结束的位置打暴力
    for(int i = l; i <= a * cnt; ++i){
        if(ar[i] % x == 0)sum++;
    }
  //第三部分 从 b块的开始到 r 打暴力
    for(int i = (b - 1) * cnt + 1; i <= r; ++i){
        if(ar[i] % x == 0)sum++;
    }
  //第三部分，计算中间到块的值
    for(int i = a + 1; i < b; ++i)sum += tr[i][x];
    return sum;
}

献上AC码：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100050 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, x, y, cnt, z;

int tr[320][MAX], ar[MAX];

int getnum(int l, int r, int x){
    int a = l / cnt + 1, b = r / cnt + 1;
    int sum = 0;
    if(a == b){
        for(int i = l; i <= r; ++i){
            if(ar[i] % x == 0)sum++;
        }
        return sum;
    }
    for(int i = l; i <= a * cnt; ++i){
        if(ar[i] % x == 0)sum++;
    }
    for(int i = (b - 1) * cnt + 1; i <= r; ++i){
        if(ar[i] % x == 0)sum++;
    }
    for(int i = a + 1; i < b; ++i)sum += tr[i][x];
    return sum;
}

int main(){
    n = IntRead();m = IntRead();
    cnt = sqrt(n);
    for(int i = 1; i <= n; ++i){
        ar[i] = IntRead();
        for(int j = 1; j * j <= ar[i]; ++j){
            if(ar[i] % j == 0){
                tr[(i - 1) / cnt + 1][j]++;
                if(ar[i] / j != j)tr[(i - 1) / cnt + 1][ar[i] / j]++;
            }
        }
    }
    while (m--) {
        x = IntRead(); y = IntRead();z = IntRead();
        cout<<getnum(x, y, z)<<endl;
    }
    return 0;
}

思路2: vector + 二分

对于这个题，数比较小，每个数都是小于1e5的，我们就可以采用枚举每个x的倍数，在给定区间去找

这里我们使用vector数组来存每个数的下标，便于二分查找，防T

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100050 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, l, r, x, a, ans;
vector<int>tr[MAX];

int main(){
    n = IntRead();m = IntRead();
    for(int i = 1; i <= n; ++i){
        x = IntRead();
        tr[x].push_back(i);//把数为x的下标塞进去
    }
    while (m--) {
        l = IntRead(); r = IntRead();x = IntRead();
        ans = 0;
        for(int i = x; i <= MAX; i += x){//这里就相当于枚举每个x的倍数
            ans += upper_bound(tr[i].begin(), tr[i].end(), r) - lower_bound(tr[i].begin(), tr[i].end(), l);
//因为是找的给定区间的，我们就去二分，前一个二分是找大于r的第一个位置，后一个二分找的是大于等于 l 的第一个位置
        }
        cout<<ans<<endl;
    }
    return 0;
}

G分割

题意：

在一个二维平面，

有n条平行于y轴的直线, 他们的x坐标是x[i]，

m条平行于x轴的直线y[i]，他们的y坐标是y[i].

求出这些直线所有可能形成矩形的总面积对1000000007取模的值。

保证所有直线不完全重叠。

思路：

面积的总和 = 能构成的本质不同的矩形的面积和

我们就可以找出所有本质不同的长和宽进行相乘并求和即可

我们举个数找下规律：

n = 5
(2 - 1) + (3 - 1) + (4 -1) + (5 - 1)
(3 - 2) + (4 - 2) + (5 - 2)
(4 - 3) + (5 - 3)
(5 - 4)
= 1 * （-4） + 2 * （-2） + 3 *（0） + 4 * （2） + 5 * （4）
1 : 0  -4
2 : 1  -3
3 : 2  -2
4 : 3  -1
5 : 4  0

对于第i个元素他的贡献值就为：

对于y也是一样的

所以我们只需要先对x 和 y数组分别升序排序，然后对x循环一遍，记录不同的x的贡献值的和ans再对y循环一遍，记录不同的y的贡献值的和cnt最后输出cnt * ans 再取模即可！

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
#define seed 1331
const int mod = 1000000007;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, m;
ll xx[MAX], yy[MAX];
ll ans, cnt;

int main(){
    io;
    cin>>n>>m;
    for(int i = 1; i <= n; ++i)cin>>xx[i];
    for(int i = 1; i <= m; ++i)cin>>yy[i];
    ans = 0;cnt = 0;
    sort(xx + 1, xx + 1 + n);
    sort(yy + 1, yy + 1 + m);
    for(int i = 1; i <= n; ++i){
        ans += xx[i] * (i * 2 - n - 1);
        ans %= mod;
    }
    for(int j = 1; j <= m; ++j){
        cnt += yy[j] * (j * 2 - m - 1);
        cnt %= mod;
    }
    cout<<(ans * cnt) % mod<<endl;
    return 0;
}

I 母牛哥与子序列

题意：

众所周知，一个序列拥有许多非空子序列。

所谓子序列就是在原序列中任意删除 0 个或多个元素，然后保持剩下元素的顺序不变所形成的序列。非空子序列集意味着剩下的子序列不能为空。

比如对于序列[1, 2, 3]，它的所有非空子序列为：[1, 2, 3]，[1, 2]，[1, 3]，[2, 3]，[1]，[2]，[3]。再比如序列 [1, 1]，它的非空子序列有：[1, 1]，[1] (删除了第一个 1)，[1] (删除了第二个1) 。

现在母牛哥手里有一个长度为 n 的正整数序列，他现在要为这个序列的所有非空子序列打分。对于一个序列而言，它的评分标准为序列里所有数的乘积（只有一个数的序列，分数就是这个数）。

母牛哥想要知道所有分数的和，但由于结果太大了，所以你只要告诉母牛哥结果对 1000000007 取模即可

思路：

打表可以发现规律：

（ ）

记得取模！

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100050 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, x;
ll ans = 1;

int main(){
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>x;
        ans *= (x + 1);
        ans %= 1000000007;
    }
    cout<<(ans - 1 + 1000000007) % 1000000007 <<endl;
    return 0;
}