UVA12983 The Battle of Chibi

$Result$

$Hyperlink$

https://www.luogu.com.cn/problem/UVA12983

$Description$

$T$组数据，每组数据给定一个长度为$n$的序列$A$，问$m$元上升子序列个数，答案对$10^9+7$取模

数据范围：$n,m\le 1000$

$Solution$

我们只关心大小关系，不关心具体数值，所以先离散化

设$f_{i,j}$表示长度为$i$，以$j$结尾的$LIS$个数，用树状数组维护转移

拓展：$n$如果大到$10^5$级别的话，如果数据纯随机构造，第一维可以只开到$\sqrt{n}$，因为$LIS$的期望长度就是$\sqrt{n}$级别的

$Code$

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 1010
#define mod 1000000007
using namespace std;int n,m,k,a[N],b[N],T,cas;
LL f[N][N],res,C[N];
inline void A(int x,LL y){for(;x<=n;x+=x&-x)C[x]+=y,C[x]%=mod;return;}
inline LL Q(int x){LL s=0;for(;x;x-=x&-x)s+=C[x],s%=mod;return s;}
inline LL read()
{LL d=1,f=0;char c;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{T=read();while(T--){n=read();k=read();for(register int i=1;i<=n;i++) b[i]=a[i]=read();sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;for(register int i=1;i<=n;i++) f[1][i]=1,a[i]=lower_bound(b+1,b+1+m,a[i])-b;for(register int i=2;i<=k;i++) {fill(C+1,C+1+n,0);for(register int j=1;j<=n;j++){f[i][j]=Q(a[j]-1);A(a[j],f[i-1][j]);}}res=0;for(register int i=k;i<=n;i++) res+=f[k][i],res%=mod;printf("Case #%d: %lld\n",++cas,res);}
}