开发施工建设网站审核,最新项目网,c 网站开发模式,国内大型网站制作灵茶八题 - 子序列 w
题目描述
给你一个长为 n n n 的数组 a a a#xff0c;输出它的所有非空子序列的元素和的元素和。
例如 a [ 1 , 2 , 3 ] a[1,2,3] a[1,2,3] 有七个非空子序列 [ 1 ] , [ 2 ] , [ 3 ] , [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 3 ] , [ 1 , 2 , 3 ] [1],[…灵茶八题 - 子序列 w
题目描述
给你一个长为 n n n 的数组 a a a输出它的所有非空子序列的元素和的元素和。
例如 a [ 1 , 2 , 3 ] a[1,2,3] a[1,2,3] 有七个非空子序列 [ 1 ] , [ 2 ] , [ 3 ] , [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 3 ] , [ 1 , 2 , 3 ] [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]元素和分别为 1 , 2 , 3 , 3 , 4 , 5 , 6 1,2,3,3,4,5,6 1,2,3,3,4,5,6所以答案为 1 2 3 3 4 5 6 24 123345624 123345624。
由于答案很大你需要输出答案模 1 0 9 7 10^97 1097 后的结果。
输入格式
第一行输入一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n\ (1\le n \le 2\cdot 10^5) n (1≤n≤2⋅105)。
第二行输入 n n n 个整数表示数组 a a a 中的元素 ( 0 ≤ a [ i ] ≤ 1 0 9 ) (0\le a[i] \le 10^9) (0≤a[i]≤109)。
输出格式
一个整数表示 a a a 的所有非空子序列的元素和的元素和模 1 0 9 7 10^97 1097 后的结果。
样例 #1
样例输入 #1
3
1 2 3样例输出 #1
24提示
对于子序列 每一个出现的次数为2的n - 1次方
#includebits/stdc.husing namespace std;typedef long long ll;
typedef pairint, intPII;
const int N2e510;
const int MOD 1e9 7;
const int INF0X3F3F3F3F;
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,-1,1,-1,1,-1,1};
const int M 1e7 10;int t;int main()
{int n;cin n;ll res 0;//对于子序列每个元素出现的次数为2的n - 1次方for(int i 1; i n; i ){int x;cin x;res x;}for(int i 1; i n - 1; i ){res res * 2 % MOD;}cout res endl;return 0;
}
