C++14(g++5.4) 解法, 执行用时: 1474ms, 内存消耗: 106812K, 提交时间: 2019-12-28 10:47:42

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
const int N=5e5+10;
int n,k,a[N],b[N];
LL f[N][15],t[15][N],ans;
LL ask(LL *t,int k) {
	LL ans=0;
	for(; k; k-=k&-k)ans+=t[k],ans%=mod;
	return ans;
}
void add(LL *t,int k,LL d) {
	for(; k<n; k+=k&-k)t[k]+=d,t[k]%=mod;
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1; i<=n; i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-b-1;
	for(int i=1; i<=n; i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	for(int i=1; i<=n; i++) {
		add(t[1],a[i],1);
		for(int j=2; j<=min(k,i); j++) {
			f[i][j]=ask(t[j-1],a[i]-1);
			add(t[j],a[i],f[i][j]);
		}
		ans+=f[i][k];
		ans%=mod;
	}
	cout<<ans<<'\n';
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1048ms, 内存消耗: 82392K, 提交时间: 2019-12-28 12:18:55

#include<bits/stdc++.h> 
using namespace std;
#define lowbit(i)  ((i)&(-i))
typedef long long ll;
const int mod=998244353; 
const int maxn=5e5+10;
ll c[maxn][20];
int n,k,a[maxn],b[maxn];
void add(int i,int x,int y)
{
	while(x<=n) c[x][i]=(c[x][i]+y)%mod,x+=lowbit(x);
}
ll getsum(int i,int x)
{
	ll res=0;
	while(x>0) res=(res+c[x][i])%mod,x-=lowbit(x);
	return res;
}
int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+1+n);
	int size=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;++i)
	a[i]=lower_bound(b+1,b+1+size,a[i])-b;
	for(int i=1;i<=n;++i)
	{
		add(1,a[i],1);
		for(int j=1;j<=min(i,k);++j)
		add(j,a[i],getsum(j-1,a[i]-1));
	}
	printf("%lld\n",getsum(k,size)%mod);
}