1085 - All Possible Increasing Subsequences

Time Limit: 3 second(s)

Memory Limit: 64 MB

An increasing subsequence from a sequence A₁, A₂ ... A_n is defined by A_i1, A_i2 ... A_ik, where the following properties hold

1. i₁ < i₂ < i₃ < ... < i_k and

2. A_i1 < A_i2 < A_i3 < ... < A_ik

Now you are given a sequence, you have to find the number of all possible increasing subsequences.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 10⁵) denoting the number of elements in the initial sequence. The next line will contain n integers separated by spaces, denoting the elements of the sequence. Each of these integers will be fit into a 32 bit signed integer.

Output

For each case of input, print the case number and the number of possible increasing subsequences modulo 1000000007.

Sample Input

Output for Sample Input

1 1 2

1 2 1000 1000 1001

1 10 11

Case 1: 5

Case 2: 23

Case 3: 7

Notes

1. For the first case, the increasing subsequences are (1), (1, 2), (1), (1, 2), 2.

2. Dataset is huge, use faster I/O methods.

题意：给你n个数，问你严格单调递增的子序列有多少个。

很水的题目吧。dp[i]——以a[i]结尾的递增子序列个数。

dp[i] = sigma(dp[j]) (1 <= j < i && a[j] < a[i])，用一个树状数组优化下就好了。

时间复杂度O(nlogn)。

方法一：sort排好序，注意相等元素的处理。映射好位置，直接就可以转移了。

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MAXN (100000+10)
#define MAXM (100000)
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d\n", (a))
#define Pf(a) printf("%.2lf\n", (a))
#define Pl(a) printf("%lld\n", (a))
#define Ps(a) printf("%s\n", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define LL long long
#define lson o<<1, l, mid
#define rson o<<1|1, mid+1, r
#define ll o<<1
#define rr o<<1|1
#define PI acos(-1.0)
using namespace std;
int dp[MAXN];
struct Node{
    int val, id;
};
Node num[MAXN];
bool cmp(Node a, Node b)
{
    if(a.val != b.val)
        return a.val < b.val;
    else
        return a.id > b.id;
}
int lowbit(int x){
    return x & (-x);
}
void update(int x, int d, int n)
{
    while(x <= n)
    {
        dp[x] += d;
        dp[x] %= MOD;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int s = 0;
    while(x > 0)
    {
        s += dp[x];
        s %= MOD;
        x -= lowbit(x);
    }
    return s;
}
int main()
{
    int t, kcase = 1;
    Ri(t);
    W(t)
    {
        int n, a; Ri(n);
        for(int i = 1; i <= n; i++)
            Ri(a), num[i].val = a, num[i].id = i;
        CLR(dp, 0); sort(num+1, num+n+1, cmp);
        for(int i = 1; i <= n; i++)
            update(num[i].id, sum(num[i].id-1)+1, n);
        printf("Case %d: %d\n", kcase++, sum(n));
    }
    return 0;
}

方法二：将元素离散化后，二分查找区间，树状数组转移。