传送门
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 和add即可（mul为乘的数，初始为1，add为加的数，初始为0）
对于操作1 : 我们取其中一个数tr[i]来看
还是 一个数乘以 a 加上 一个数的形式我们需要更新mul 和 add 的值
- 对于操作2 同理，我们只需要跟新add的值即可
要注意，我们输出的时候是输出，所以对于新加入的元素p，他想要进入这个数组，就必须转换成
的形式，也即是将 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个贝壳进行分块，每一块的大小不超过，然后像线段树求区间和一样一段段的求即可
分块操作：我这里选择的是输入的时候就直接分块，你也可以像其他人那样写个函数，等输入完了再分
分块的时候最好是从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多，因为分的块最大也就是
- l 和 r 不在一个块里面，这个时候就分三部分进行运算
在这里插入图片描述
见图：由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;
}
京公网安备 11010502036488号