期望＋DP ZOJ 3929 Deque and Balls

题意：给你n个数，按照顺序依次放入一个双端队列（可放在头部，也可以放在尾部），求xi > xi+1的期望 * 2^n mod (1e9 +7)

分析：期望＊２＾n＝出现这种排法的概率＊这种排法的desents数*2^n = 1/(2^(n-1)) * 2^n * 每一种排法每一个数字的贡献值．

首先插入xi有两种方法，相当于有两种排法，那么求前缀时ans[i] = ans[i-1] * 2，然后再考虑当前xi的贡献值：如果放在头部，那么要求出满足xi>xj的xj的出现次数和，然后发现第一个数字出现１次，第二个２次，第三个４次，８，16．．．放在尾部同理，用树状数组累计次数和，至于i之后的数字如何排都不会对当前i做贡献,所以*.

#include <bits/stdc++.h>

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

template<class T>
void add(T &a, T b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

struct BIT {
    int c[N];
    int n;
    void init(int n) {
        this->n = n;
        std::fill (c, c+1+n, 0);
    }
    void updata(int p, int v) {
        for (int i=p; i<=n; i+=i&-i) {
            add (c[i], v);
        }
    }
    int query(int p) {
        int ret = 0;
        for (int i=p; i>0; i-=i&-i) {
            add (ret, c[i]);
        }
        return ret;
    }
};
BIT L, R;

int a[N], cnt[N];

int pow_mod(int x, int n) {
    int ret = 1;
    while (n) {
        if (n & 1) {
            ret = 1ll * ret * x % MOD;
        }
        x = 1ll * x * x % MOD; n >>= 1;
    }
    return ret;
}

void pre_init() {
    cnt[1] = cnt[2] = 1;
    for (int i=3; i<=100000; ++i) {
        cnt[i] = 1ll * cnt[i-1] * 2 % MOD;
    }
}

int main() {
    pre_init ();
    int T; scanf ("%d", &T);
    while (T--) {
        int n; scanf ("%d", &n);
        int nn = n + 3;
        L.init (nn); R.init (nn);
        for (int i=1; i<=n; ++i) {
            scanf ("%d", a+i);
        }
        long long ans = 0;
        for (int i=1; i<=n; ++i) {
            long long tmp = 0LL + L.query (a[i] - 1) + R.query (nn-a[i]-1);
            tmp = tmp * pow_mod (2, n - i) % MOD;
            add (ans, tmp);
            L.updata (a[i], cnt[i]);
            R.updata (nn - a[i], cnt[i]);
        }
        ans = ans * 2 % MOD;
        std::cout << ans << '
';
    }

    return 0;
}

期望＋DP ZOJ 3929 Deque and Balls

相关推荐