AtCoder Beginner Contest 221 E

题意:

给定一个序列,问有多少个非空子集满足如下要求:

1. 子集元素的个数不少于2。

2. AtCoder Beginner Contest 221 E,即子集第一个元素不大于最后一个元素。

分析:

我们知道n个元素有AtCoder Beginner Contest 221 E个非空子集。

设第一个元素为AtCoder Beginner Contest 221 E最后一个元素为AtCoder Beginner Contest 221 E,这两个元素之间就有AtCoder Beginner Contest 221 E个元素。

那么以AtCoder Beginner Contest 221 E为第一个元素,以AtCoder Beginner Contest 221 E为最后一个元素的子集就有AtCoder Beginner Contest 221 E个。

枚举AtCoder Beginner Contest 221 E,最后的答案就是AtCoder Beginner Contest 221 E

将这个公式转化一下,每次枚举i的时候,可以先算出AtCoder Beginner Contest 221 E,然后在乘上AtCoder Beginner Contest 221 E

因为要对区间和做修改,所以用树状数组来存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;
}

上一篇:PTA 练习2-17 生成3的乘方表 (15 分)


下一篇:羊城杯 2021 | Crypto