Problem 2236 第十四个目标

Accept: 109    Submit: 302

Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

目暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算，柯南追踪伤害阿笠博士的凶手，根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经过一系列的推理后，柯南发现受害者的名字均包含扑克牌的数值，且扑克牌的大小是严格递增的，此外遇害者与毛利小五郎有关。

为了避免下一个遇害者的出现，柯南将可能遭到暗算的人中的数字按关联程度排列了出来，即顺序不可改变。柯南需要知道共有多少种可能结果，满足受害人名字出现的数字严格递增，但是他柯南要找出关键的证据所在，所以这个任务就交给你了。

(如果你看不懂上面在说什么，这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。)

Input

多组数据(<=10)，处理到EOF。

第一行输入正整数N(N≤100 000)，表示共有N个人。

第二行共有N个整数Ai(1≤Ai≤10^9)，表示第i个人名字中的数字。

 

Output

每组数据输出一个整数，表示所有可能的结果。由于结果可能较大，对1 000 000 007取模后输出。

Sample Input

3 1 3 2

Sample Output

5

Source

福州大学第十三届程序设计竞赛 

 

树状数组好题目，然而我就是个智障

1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=100005; 5 const int MOD=1000000007; 6 int n; 7 int a[MAX],b[MAX],c[MAX],f[MAX]; 8 void add(int x,int y){
     for (x;x<=MAX;x+=(x&-x)) c[x]=(c[x]+y)%MOD;} 9 int search(int x){
     int an(0);for (;x>0;x-=(x&-x))an=(an+c[x])%MOD;return an;}10 int halfs(int x){11     int low,high,mid;12     low=1,high=n;13     while (low<=high){14         mid=(low+high)>>1;15         if (b[mid]<=x)16          low=mid+1;17         else18          high=mid-1;19     }20     return low-1;21 }22 int main(){23     freopen ("point.in","r",stdin);24     freopen ("point.out","w",stdout);25     int i,j,k,ans;26     while (~scanf("%d",&n)){27         memset(c,0,sizeof(c));28         ans=0;29         for (i=1;i<=n;i++){30             scanf("%d",a+i);31             b[i]=a[i];32         }33         sort(b+1,b+n+1);34         for (i=1;i<=n;i++){35             k=halfs(a[i]);36             f[i]=search(k-1)+1;37             ans=(ans+f[i])%MOD;38             add(k,f[i]);39         }40         printf("%d\n",ans);41     }42     return 0;43 }