思路：快速幂

本题是Python快乐题，Java和C++选手被爆int坑的很惨~

首先考虑每个元素都被处理过$q$次

那么对于$q_i=x$，则有第$x$个元素处理次数-1

然后统计最终每个元素被处理多多少次，处理过几次，就是乘多少个2，这里我们可以使用快速幂计算，除以取模，以防溢出。

对于Python选手可以直接使用库函数pow，对应的复杂度也为$logn$

整体时间复杂度：$O(nlogn)$

C++

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int qpow(int a,int b,int mod){
    long long res=1,t=a;
    while(b){
        if(b&1){
            res=1ll*(res*t)%mod;
        }
        b>>=1;
        t=(t*t)%mod;
    }
    return res;
}
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> s(n + 1, q);
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        s[x] -= 1;
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        res=(res+1ll*qpow(2, s[i + 1],mod)* a[i] % mod)%mod;
    }
    cout << res << endl;
    return 0;
}

Java

import java.util.*;
import java.math.*;

public class Main {
    static final int mod = (int) Math.pow(10, 9) + 7;

    static long qpow(int a, int b, int mod) {
        long res = 1, t = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * t) % mod;
            }
            b >>= 1;
            t = (t * t) % mod;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        int[] s = new int[n + 1];
        Arrays.fill(s, q);
        for (int i = 0; i < q; i++) {
            int x = scanner.nextInt();
            s[x] -= 1;
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + qpow(2, s[i + 1], mod) * a[i] % mod) % mod;
        }
        System.out.println(res);
    }
}

Python

n, q = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
s = [q] * (n + 1)
for _ in range(q):
    x = int(input())
    s[x] -= 1
res = 0
for i in range(n):
    res += pow(2, s[i + 1], mod) * a[i] % mod
    res %= mod
print(res)

题目描述

小美拿到了一个数组，她每次操作会将除了第$x$个元素的其余元素翻倍，一共操作了$q$次。请你帮小美计算操作结束后所有元素之和。 由于答案过大，请对$10^9+7$取模。

输入描述

输入描述

第一行输入两个正整数$n,q$，代表数组的大小和操作次数。

第二行输入$n$个正整数$a_i$，代表数组的元素。

接下来的$q$行，每行输入一个正整数$q_i$，代表第$i$次操作未被翻倍的元素。

$1\le n,q\le 10^5$

$1\le x_i\le n$

$1\le a_i\le 10^9$

输出描述

一个整数，代表操作结束后所有元素之和模$10^9+ 7$的值。

样例

输入

4 2
1 2 3 4
1
2

输出

34