题意:
给定一个序列,问有多少个非空子集满足如下要求:
1. 子集元素的个数不少于2。
2. ,即子集第一个元素不大于最后一个元素。
分析:
我们知道n个元素有个非空子集。
设第一个元素为最后一个元素为,这两个元素之间就有个元素。
那么以为第一个元素,以为最后一个元素的子集就有个。
枚举,最后的答案就是。
将这个公式转化一下,每次枚举i的时候,可以先算出,然后在乘上。
因为要对区间和做修改,所以用树状数组来存2的幂次方的求和。
数据范围太大,但是n的范围在3e5,所以需要离散化
代码如下:
LL tr[N], Pow[N];
//Pow数组预处理出2的幂次方
int n, tot;
int a[N];
vector<int> alls;
void modify(int x, LL c)
{
for (int i = x; i <= tot; i += lowbit(i))
tr[i] = (tr[i] + c) % mod;
}
LL query(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i))
res = (tr[i] + res) % mod;
return res;
}
int find(int x)
{
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
LL ksm(LL base, LL p)
{
LL res = 1;
while (p)
{
if (p & 1) res = res * base % mod;
base = base * base % mod;
p >>= 1;
}
return res % mod;
}
int main ()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
alls.push_back(a[i]);
Pow[i] = ksm(2, i);
}
//离散化
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
tot = alls.size();
for (int i = 1; i <= n; i ++ ) modify(find(a[i]), Pow[i]);
LL ans = 0;
for (int i = 1; i <= n; i ++ )
{
int pos = find(a[i]);
//每次计算2的j次方求和时先将当前枚举到的去掉
//+mod避免出现负数
modify(pos, -Pow[i] + mod);
//避免出现负数加模再取模
LL tmp = (query(tot) - query(pos - 1) + mod) % mod;
//求逆元
ans += tmp * ksm(Pow[i + 1], mod - 2);
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}