题目分析
不难分析出来,我们就是要求出,对每一个位置i
而言,其后面的比它大的位置j1
,j2
.....jn
,构成的数学式子求解。
我们可以对式子进行化简。
\[ans[i]=\frac{2^{j_1-1}+2^{j_2-1}+...2^{j_n-1}}{2_i} \]然后,emm,我就卡在这里了,因为这时就要求出i之后所有比它大的位置。
但是,我忽略了一个很重要的思想,正着想不行的时候,我们可以尝试反着想。
如果,我们要求的是一个数前面所有比它小的位置
,会有出路嘛?
我们可以很快的发现,当要找一个数前面比他小的位置来求答案时,我们要求的式子就变成了
\[ans[j]=2^{j-1}(\frac{1}{2^{i_1}}+\frac{1}{2^{i_2}}+...+\frac{1}{2^{i_n}}) \]那接下来要解决的问题就是,括号里面的怎么求?
这时,就简单了,我们可以用树状数组进行优化。在树状数组中,考虑每个位置时,在w[j]上插入对应的式子。这样正向扫描时,这样sum(w[j])就是前面比它小的位置上就是对应的式子的和(即括号里的内容)了。
AcCode
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const LL N = 3e5 + 10,mod=998244353;
LL tr[N];
int w[N];
int n;
int lowbit(int x)
{
return x & (-x);
}
void add(int x,LL c)
{
for(int i=x;i<=n;i+=lowbit(i))
{
tr[i]=(tr[i]+c)%mod;
}
}
LL sum(int x)
{
LL res = 0;
for(int i=x;i;i-=lowbit(i))
{
res=(res+tr[i])%mod;
}
return res;
}
LL ksm(LL a,LL b)
{
LL res = 1;
while(b)
{
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
void init()
{
map<int,int> mp;
for(int i=1;i<=n;i++)
mp[w[i]]=0;
int sz=0;
for(auto &p:mp) p.second=++sz;
for(int i=1;i<=n;i++) w[i]=mp[w[i]];
}
int main()
{
const LL div = ksm(2,mod-2);
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
LL ans = 0;
init();
for(int i=1; i<=n; i++){
ans += sum(w[i])*ksm(2,i-1);
ans %= mod;
add(w[i],ksm(div,i));
}
cout<<ans<<endl;
return 0;
}