题目描述：给定由1-n组成的长度为n的a[]和k，问长度为k+1的子序列中有多少个单调递增的？
n<=1e5,k<=10

终于想到了！
开k+1个线段树/树状数组
记f[i][j][o]为前i个数，以j结尾，长度为o的子序列有多少个。
i维可以省略，f[j][o]=f[Σ1-(j-1)][o-1],所以用树状数组维护f数组（写成了c）

所求答案即为f[1~n][k+1].
复杂度O(knlogn)

```
#include<bits stdc++.h>
#define ll long long
using namespace std;
ll a[100010];
ll c[100010][15];
ll n,k;
ll lowbit(ll i){return i&(-i);}
void add(ll i,ll j,ll v)
{
while(i<=n)
{
c[i][j]+=v;
i+=lowbit(i);
}
}
ll getsum(ll i,ll j)
{
ll sum=0;
while(i)
{
sum+=c[i][j];
i-=lowbit(i);
}
return sum;
}
int main()
{
cin>>n>>k;
++k;
for(ll i=1;i<=n;++i)
{
cin>>a[i];
}
ll ans=0,x;
for(ll i=1;i<=n;++i)
{
add(a[i],1,1);
for(ll j=2;j<=k;++j)
{
add(a[i],j,getsum(a[i]-1,j-1));
}
}
cout<