灵茶八题 - 子序列 +w+

灵茶八题 - 子序列 +w+

题目描述

给你一个长为 $n$ 的数组 $a$，输出它的所有非空子序列的元素和的元素和。

例如 $a=[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=24$。

由于答案很大，你需要输出答案模 $10^9+7$ 后的结果。

输入格式

第一行输入一个整数 $n(1\le n\le 2\cdot 10^5)$。

第二行输入 $n$ 个整数，表示数组 $a$ 中的元素 $(0\le a[i]\le 10^9)$。

输出格式

一个整数，表示 $a$ 的所有非空子序列的元素和的元素和，模 $10^9+7$ 后的结果。

样例 #1

样例输入 #1

3
1 2 3
1
2

样例输出 #1

24
1

提示

对于子序列， 每一个出现的次数为2的n - 1次方

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=2e5+10;
const int MOD = 1e9 + 7;
const int INF=0X3F3F3F3F;
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34