C++11(clang++ 3.9) 解法, 执行用时: 446ms, 内存消耗: 10480K, 提交时间: 2020-04-03 23:05:05

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 55, mod = 1e9 + 7;

int n, m, a[N], tr[N][M], idx;
set<int> S;
unordered_map<int, int> h;

inline int lowbit(int x){
	return x & -x;
}

void add(int x, int c, int p){
	for(int i = x; i <= idx; i += lowbit(i)) (tr[i][p] += c) %= mod;
}

int sum(int x, int p){
	int res = 0;
	for(int i = x; i; i -= lowbit(i)) (res += tr[i][p]) %= mod;
	return res;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", a + i), S.insert(a[i]);
	for(auto &x : S) h[x] = ++idx;
	for(int i = 1; i <= n; i++){
		int k = h[a[i]];
		add(k, 1, 1);
		for(int j = 2; j <= m; j++) add(k, sum(k - 1, j - 1), j);
	}
	printf("%d", sum(idx, m));
}

C++14(g++5.4) 解法, 执行用时: 527ms, 内存消耗: 14796K, 提交时间: 2020-04-04 20:02:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+5;
ll c[maxn][52],a[maxn],b[maxn];
void add(ll x,ll k,ll v){
    for(;x<maxn;x+=x&(-x)) (c[x][k]+=v)%=mod;
}
ll sum(ll x,ll k){
    ll ans=0;
    for(;x;x-=x&(-x)) (ans+=c[x][k])%=mod;
    return ans;
}
int main(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
    for(int i=1;i<=n;i++){
        add(a[i],1,1);
        for(int j=2;j<=k;j++){
            add(a[i],j,sum(a[i]-1,j-1));
        }
    }
    cout<<sum(n,k)<<endl;
    return 0;
}