ZOJ 3932 Deque and Balls

2696 단어 dpZOJanddequeB3932
There are n balls, where the i-th ball is labeled as pi. You are going to put n balls into a deque. In the i-th turn, you need to put the i-th ball to the deque. Each ball will be put to both ends of the deque with equal probability.
Let the sequence (x1, x2, ..., xn) be the labels of the balls in the deque from left to right. The beauty of the deque B(x1, x2, ..., xn) is defined as the number of descents in the sequence. For the sequence (x1, x2, ..., xn), a descent is a position i (1 ≤ i < n) with xi > xi+1.
You need to find the expected value of B(x1, x2, ..., xn).
Deque is a double-ended queue for which elements can be added to or removed from either the front (head) or the back (tail).

Input


There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (2 ≤ n ≤ 100000) -- the number of balls. The second line contains n integers: p1, p2, ..., pn (1 ≤ pi ≤ n).

Output


For each test case, if the expected value is E, you should output E⋅2n mod (109 + 7).

Sample Input

2
2
1 2
3
2 2 2

Sample Output

2

0

DP , a[i], , 。 i-1

*2, , ,

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long LL;
const LL  mod=1e9+7;
#define MAX 100000
LL dp[MAX+5];
LL p[MAX+5];
LL num[MAX+5];
int n;
int fun()
{
    p[0]=0;p[1]=1;
    for(int i=2;i<=MAX+5;i++)
    {
        p[i]=(p[i-1]*2)%mod;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    int a;
    fun();
    while(t--)
    {
        scanf("%d",&n);
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            dp[i]=(2*dp[i-1]+p[i-1]-num[a]+mod)%mod;
            if(i==1)
                 num[a]=(num[a]+1)%mod;
            else
                 num[a]=(num[a]+p[i-1])%mod;

        }
        dp[n]=(dp[n]*2)%mod;
        printf("%lld
",dp[n]); } return 0; }

좋은 웹페이지 즐겨찾기