dp[i][j]表示以a[i]结尾的长度为j的上升子序列个数。
方程：dp[i][j]=sum(dp[k][j-1])，a[k]
求解目标：sum(dp[k][m])，1<=k<=n。
三层循环枚举的话要超时，观察式子，相当于是统计前缀和，这启示我们可以用到树状数组来优化，复杂度mnlogn。
值域较大，要使用离散化。
1 #include
2 #include
3 #include
4 #define mod 123456789
5 typedef long long ll;
6 using namespace std;
7 #define N 10005
8
9 ll a[N],b[N];
10 ll dp[N][105];
11 int n,m,len;
12
13 int lowbit(int x){
14 return x&(-x);
15 }
16
17 void add(int i,int j,ll val){
18 while(i<=len){
19 dp[i][j]=(dp[i][j]+val)%mod;
20 i+=lowbit(i);
21 }
22 }
23
24 ll query(int i,int j){
25 ll res=0;
26 while(i){
27 res=(res+dp[i][j])%mod;
28 i-=lowbit(i);
29 }
30 return res;
31 }
32
33
34
35 int main(){
36 while(~scanf("%d%d",&n,&m)){
37 for(int i=1;i<=n;i++){
38 scanf("%lld",&a[i]);
39 b[i]=a[i];
40 }
41 memset(dp,0,sizeof(dp));
42 sort(b+1,b+n+1);
43 len=unique(b+1,b+n+1)-b-1;
44 for(int i=1;i<=n;i++){
45 int pos=lower_bound(b+1,b+len+1,a[i])-b;
46 add(pos,1,1);
47 for(int j=2;j<=m;j++){
48 int sum=query(pos-1,j-1);
49 add(pos,j,sum);
50 }
51 }
52 printf("%lld\n",query(len,m));
53 }
54 return 0;
55 }