题意：给定1～n的一种排列，求长度为k+1的上升子序列的个数。 (0 <= k <= 10 , n <= 1e5, 答案小于8e18)
题解：DP。首先可以很容易的想到DP[i][j]，表示以i为结尾，长度为j的上升子序列的个数。
也可以很容易的想到转移 DP[i][j] = sum(DP[k][j-1]) ( k < i && num[k] < num[i] )。
但是我们也可以很容易的发现，这个转移太慢了，一次转移是O(n)的。
接下来就是优化这个转移了。
由于是1～n的排列，而且n<=1e5，我们考虑用k+1棵树状数组优化这个求和。
只需要在第k棵树状数组中用num[i]+1号节点维护dp[i][k]即可。
加1是因为考虑到树状数组无法维护0节点，即无法维护初始状态dp[0][0] = 1，所以全部加1考虑，用1号节点维护DP[0][0]。
这样做之后如何转移呢？
由于我们按num[i]的大小维护树状数组，现在要求出sum(DP[k][j-1]) ( k < i && num[k] < num[i] )，答案就是getsum(num[i], j-1)，表示用第j-1棵树状数组中求num[i]+1左边的所有的节点的和（别忘记我们用num[i]+1号节点维护num[i]），同时DP[i]是从左往右扫的，时间戳k < i是自动维护好的。求出DP值之后再维护树节点，update(num[i]+1, DP[i][j], j) 表示把DP[i][j]的值扔进第j棵树状数组的num[i]+1节点，这样成功把转移做到了logN。
实际上我们根据以上的getsum和update的转移方法，连DP数组都可以省略了，答案就是getsum(n+1, k+1)。
这样，这题就解决了，很有意思的题。
只要k不大，即使不是排列，我们离散化依然可以做，然而求最长上升子序列的个数就需要别的办法了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, k;
ll tree[N][15] = {0};
int f(int x){ return x&-x; }
void update(int p, ll v, int k) { for(; p <= n+1; p += f(p)) tree[p][k] += v; }
ll getsum(int p, int k){
ll res = 0;
for(; p; p -= f(p)) res += tree[p][k];
return res;
}
int main(){
scanf("%d%d", &n, &k);
update(1, 1, 0);
for(int i = 1; i <= n; ++i){
ll num;
scanf("%lld", &num);
for(int j = 1; j <= k+1; ++j){
ll sum = getsum(num, j-1); // 在第j-1棵树状数组中求出DP[i][j]
update(num+1, sum, j); // 把DP[i][j]扔进第j棵树状数组
}
}
printf("%lld\n", getsum(n+1, k+1));
}