?

題目鏈接

題意：給你n個數(shù)，按照順序依次放入一個雙端隊(duì)列（可放在頭部，也可以放在尾部），求xi > xi+1的期望 * 2^n mod (1e9 +7)

分析：期望＊２＾n＝出現(xiàn)這種排法的概率＊這種排法的desents數(shù)*2^n = 1/(2^(n-1)) * 2^n *?每一種排法每一個數(shù)的desents數(shù)＝２＊　每一種排法每一個數(shù)字的貢獻(xiàn)值．

首先插入xi有兩種方法，相當(dāng)于有兩種排法，那么求前綴時(shí)ans[i] = ans[i-1] * 2，然后再考慮當(dāng)前xi的貢獻(xiàn)值：如果放在頭部，那么要求出滿足xi>xj的xj的出現(xiàn)次數(shù)和，然后發(fā)現(xiàn)第一個數(shù)字出現(xiàn)１次，第二個２次，第三個４次，８，16．．．放在尾部同理，用樹狀數(shù)組累計(jì)次數(shù)和，至于i之后的數(shù)字如何排都不會對當(dāng)前i做貢獻(xiàn),所以*.

#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 << '\n';}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/5387417.html

總結(jié)

以上是生活随笔為你收集整理的期望＋DP ZOJ 3929 Deque and Balls的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。