题意

给你有$n$个不同元素的序列，找出长度为$k+1$的上升子序列
序列中的元素值不超过$n$
其中$1 \le n \le 10^5$ , $0 \le k \le 10$
题目保证答案不超过$8 \cdot 10^{18}$

思路

dp[i][t]表示长度为t的以i结尾的上升子序列个数。
因此有dp转移方程：
dp[i][1]=1
dp[i][t]=dp[j][t-1] , j<i && a[j]<a[i]
然而这样不满足时间要求，需要优化。
考虑用树状数组快速更新，我们用dp[i][t]表示以值为i结尾的长度为t的上升子序列个数。
那么我们用树状数组可以快速求出dp[1][t-1]~dp[i-1][t-1]的和。
这样我们就能在$O(logn)$时间内更新dp[i][j]。
总时间复杂度$O(nlogn)$.

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e5+7;
typedef long long ll;
ll dp[Nmax][15];
int n,k;
int a[Nmax];
struct BIT
{
    inline int lowbit(int x)
    {
        return x&(-x);
    }

    void update(int pos,int t,ll add)//注意add应为long long类型，否则wa
    {
        while(pos<=n)
            dp[pos][t]+=add,pos+=lowbit(pos);
    }

    ll get_sum(int pos,int t)
    {
        ll ans=0LL;
        while(pos)
            ans+=dp[pos][t],pos-=lowbit(pos);
        return ans;
    }

}bit;

int main()
{
    scanf("%d%d",&n,&k);  
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        bit.update(a[i],1,1);
        for(int t=2;t<=k+1;t++)
            bit.update(a[i],t,bit.get_sum(a[i]-1,t-1));
    }
    printf("%lld\n",bit.get_sum(n,k+1));

    //暴力
#ifdef baoli
    for(int i=1;i<=n;i++)
        for(int t=2;t<=k+1;t++)
            for(int j=1;j<i;j++)
                if(a[j]<a[i])
                    dp[i][t]+=dp[j][t-1];
    ll ans=0LL;
    for(int i=1;i<=n;i++)
        ans+=dp[i][k+1];
    printf("%lld\n",ans);
#endif
    return 0;
}