Codeforces Global Round 27

ABC 略

D

将每个数拆成x*2的整数次幂，一个直接的想法是尽量把2的整数次幂给大的数。那么所有乘上2的整数次幂的数构成的序列单调递减，反证法，如果序列中存在i j 使得a[i]<a[j]，那么我们不如把给a[i]乘的2的幂给a[j]乘。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int T,n,a[N],b[N],sta[N],st[N],cnt,sum,s;
void init()
{
	cnt=sum=s=0;
	for(int i=1;i<=n;i++) b[i]=0;
}
int power(int x,int y)
{
	int ans=1,w=x;
	for(;y;y>>=1)
	{
		if(y&1) ans=(ans*w)%mod;
		w=w*w%mod;
	}
	return ans%mod;
}
bool pd(int x,int y,int z)
{
	int ans=x,w=2;
	for(;y;y>>=1)
	{
		if(y&1)
		{
			if(ans*w>1e9) return true;
			ans=ans*w;
		}
		w=w*w;
	}
	if(ans>z) return true;
	return false;
}
void solve()
{
	cin>>n;
	init();
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		while(a[i]%2==0&&a[i]>1)
		{
			a[i]/=2;
			b[i]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		while(cnt&&pd(a[i],b[i],sta[cnt]))
		{
			b[i]=(b[i]+st[cnt])%mod;
			s=(s+sta[cnt])%mod;
			sum=(sum-sta[cnt]*power(2,st[cnt])+mod)%mod;
			cnt--;
		}
		sta[++cnt]=a[i];
		st[cnt]=b[i];
		sum=(sum+a[i]*power(2,b[i]))%mod;
		cout<<(sum+s)%mod<<" ";
	}
	cout<<endl;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--) solve();
}