题意：给定一个序列从左往右对于每个索引
i
i
i，求出其前缀的数组可以进行任意次以下操作的条件下：选择
j
<
=
k
且
k
<
=
i
且
a
j
m
o
d
2
=
0
，令
a
k
=
a
k
∗
2
，
a
j
=
a
j
/
2
j<=k且k<=i且a_j \mod 2 = 0，令a_k=a_k*2，a_j=a_j/2
j<=k且k<=i且ajmod2=0，令ak=ak∗2，aj=aj/2，可能获得的最大前缀和
每一个数只能从它的前面获得乘以2的次数，这很重要，考虑下面的一个序列
原数列： 4 2 5 2 7
能除则除2后：1 1 3 1 7
数组下标从1开始，假如目前遍历到
i
=
3
i = 3
i=3，我们肯定是想要把前面所有的乘2次数都贪心的乘给3，因为3最大，这样可以使每个乘2有更大的收益；再遍历到
i
=
5
i = 5
i=5呢？首先，对于
i
=
3
→
5
i=3\to5
i=3→5之间的乘2次数，我们给不了3去乘，那显然给7去乘，乘了之后，我们发现
7
→
14
7\to14
7→14，那对于
i
=
3
i=3
i=3前面的2，我们是不是应该乘给这个14，这样乘2的收益更大；再假设
i
=
5
i=5
i=5时
a
5
=
1
a_5=1
a5=1，这个时候我们用掉3~5之间的2之后，
a
5
=
2
a_5=2
a5=2，
a
3
>
a
5
a_3>a_5
a3>a5的，这个时候
i
=
3
i=3
i=3前面的2肯定乘给
a
3
a_3
a3更优
可以用单调栈维护这个过程，使得栈顶元素的
b
t
o
p
∗
2
c
[
t
o
p
]
−
c
[
p
r
e
]
b_{top}*2^{c[top]-c[pre]}
btop∗2c[top]−c[pre]是栈中最大的，其中
b
b
b数组表示除2后的序列数，
c
c
c数组表示乘2次数的前缀和，每次对于
i
i
i，维护这个栈顶是否要弹出，弹出这一操作就是上面例子的第一个情况，随时维护答案
a
n
s
ans
ans，弹出栈需要减去贡献，每个
i
i
i加入都要计算新的贡献
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
const ll mod = 1e9 + 7;
int n;
cin >> n;
vector<ll> a(n + 1), b(n + 1), p_rem(n + 1), c(n + 1);
// p_rem 记录前面都除以2之后的剩余数的前缀和
// c统计除以2的次数(前缀)
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i];
while (b[i] % 2 == 0)
{
b[i] /= 2;
c[i]++;
}
c[i] += c[i - 1];
p_rem[i] = (p_rem[i - 1] + b[i]) % mod;
}
auto ksm = [&](ll a, ll b) -> ll
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
};
auto cmp = [&](ll a, ll b, ll c) -> bool
{
if (c >= 30) // 大于1e9，直接不用比了
return true;
return a <= b * (1LL << c);
};
// 单调栈
stack<ll> st; // 应该存上一个终点的坐标
ll sum = 0;
for (int i = 1; i <= n; i++)
{
// 维护单调栈
while (!st.empty() && cmp(b[st.top()], b[i], c[i] - c[st.top()]))
{
// 如果更优，删掉之前的区间的贡献
int lst = 0, now = st.top();
st.pop();
if (st.size())
lst = st.top();
sum -= (b[now] * ksm(2, c[now] - c[lst]) - b[now]);
}
if (st.size()) // 加上当前贡献
sum += b[i] * ksm(2, c[i] - c[st.top()]) - b[i];
else
sum += b[i] * ksm(2, c[i]) - b[i];
st.push(i);
cout << (sum % mod + p_rem[i] + mod) % mod << " ";
}
cout << '\n';
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
cout << endl;
// system("pause");
return 0;
}