``` #include<bits/stdc++.h> using namespace std; using ll=long long; const ll p=1e9+7; const int N=1e6+5; int a[N],b[N]; ll qmi(ll x,ll y){//快速幂 ll res=1; while(y){ if(y&1){ res=res*x%p; } y>>=1; x=x*x%p; } return res; } int main(){ int n,q;cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=q;//记录下每个数本来要翻倍多少次 } while(q--){ int x;cin>>x;//对这些数少一次翻倍次数 b[x]--; } ll sum=0; for(int i=1;i<=n;i++){ sum=(sum%p+a[i]*qmi(2,b[i])%p)%p;//计算和 } cout<<sum<<endl; return 0; } ```

对于所有的数, 最多需要乘以 $2^q$ 次, (即 翻 $q$ 倍) 而接下来q行输入的是不需要被翻倍的数, 每被指明不需要翻倍一次, 我们就对它进行计数一次, 如果 arr[i] 被 指明不需要翻倍que[i]次, 则最终它只需要翻倍q - que[i]次 即 $arr[i] \times 2^{q - que[i]}$ 则 $sum = (\sum_{i=0}^{n-1}arr[i] \times 2^{q - que[i]}) \mod (1e9+7)$ 代码如下: ```cqq #include <cstdio> #include <vector> using namespace std; int mod = 1e9 + 7; using ll = long long; ll ppow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; } int main() { int n, q; scanf("%d %d", &n, &q); vector<int> arr(n); for (int i = 0; i < n; ++i) scanf("%d", &arr[i]); vector<int> que(n, 0); for (int i = 0; i < q; ++i) { int j; scanf("%d", &j); ++que[j - 1]; } long long sum = 0; for (int i = 0; i < n; ++i) { sum = (sum + arr[i] * ppow(2, q - que[i])) % mod; } printf("%lld\n", sum); return 0; } ``` 使用快速幂计算一个数为 $logN$, 计算 n 个数 为 O(NlogN) (时间复杂度)