题意：
问你有多少个上升子序列。（题意很坑爹！）
分析：首先要离散化，因为数是int范围，而数最多时有1e5个。然后就是递推。类似于hdu5904的递推过程http://acm.hdu.edu.cn/showproblem.php?pid=5904
因为以一个数结尾的递增子序列只能来自上一个递增子序列的个数，即求所有以比结尾数小的数为结尾的子序列个数之和。（有点绕。。）
注意：在更新的时候就需要取模，如果考虑一个严格单调递增的序列，那么以第n个数为最后一个数结尾的单调递增子序列就会有2的n-1次个。所以需要在更新中就取模
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100005;
const long long mod = 1000000007;
long long C[maxn];
int a[maxn];
struct Node
{
int num, index;
}node[maxn];
bool cmp(Node p, Node q)
{
return p.num < q.num;
}
int lowbit(int lo)
{
return lo & (-lo);
}
void modify(int pos, long long value)
{
while(pos < maxn)
{
C[pos] = (value + C[pos]) % mod;
pos += lowbit(pos);
}
}
long long getsum(int pos)
{
long long sum = 0;
while(pos > 0)
{
sum = (sum + C[pos]) % mod;
pos -= lowbit(pos);
}
return sum % mod;
}
int main()
{
int T, n;
scanf("%d", &T);
for(int t = 1; t <= T; t++)
{
scanf("%d", &n);
long long ans = 0;
int cnt = 1, pre;
for(int i = 1; i <= n; i++)
{
scanf("%d", &node[i].num);
node[i].index = i;
}
sort(node + 1, node + n + 1, cmp);
a[node[1].index] = cnt;
pre = node[1].num;
for(int i = 2; i <= n; i++)
{
if(pre == node[i].num)
a[node[i].index] = cnt;
else
{
a[node[i].index] = ++cnt;
pre = node[i].num;
}
}
memset(C, 0, sizeof(C));
for(int i = 1; i <= n; i++)
{
int tem;
tem = a[i];
tem++;
int sum = getsum(tem - 1);
ans += (sum + 1);
modify(tem, sum + 1);
}
ans = ans % mod;
printf("Case %d: %lld\n", t, ans);
}
return 0;
}