1 #include <algorithm> 2 using namespace std; 3 typedef long long LL; 4 const int N = 10000 + 10; 5  6 LL a[N],b[N],c[N]; 7 int n; 8 LL dp[N][N]; 9 int lowbit(int t)10 {11     return t & (-t);12 }13 void update(int pos, LL val)14 {15     while(pos <= n)16     {17         c[pos] += val;18         pos += lowbit(pos);19     }20 }21 LL query(int pos)22 {23     LL ans = 0;24     while(pos >= 1)25     {26         ans += c[pos] % 123456789;27         pos -= lowbit(pos);28     }29     return ans;30 }31 int main()32 {33     int  m, i, j;34     while(scanf("%d%d",&n, &m) != EOF)35     {36         memset(dp, 0, sizeof(dp));37 38         for(i=1; i<=n; ++i)39         {40             dp[i][1] = 1;41             scanf("%I64d",&a[i]);42             b[i] = a[i];43         }44         sort(b+1, b+n+1);45         for(j=2; j<=m; ++j)46         {47             memset(c, 0, sizeof(c));48             for(i=1; i<=n; ++i)49             {50                 int index = lower_bound(b+1, b+n+1,a[i]) - b ;//离散化，index 表示a[i]在数列中第几大51                 dp[i][j] = query(index-1);//找出小于index的长度为j-1的递增子序列有多少个52                 update(index,dp[i][j-1]);//更新以i结尾的，长度为j-1的递增子序列有多少个53             }54         }55         LL ans = 0;56         for(i=1; i<=n; ++i)57             ans = (ans + dp[i][m]) % 123456789;58         printf("%I64d\n",ans);59     }60 }