pypy3 解法, 执行用时: 631ms, 内存消耗: 80044K, 提交时间: 2021-06-01 03:08:19

MOD = int(1e9 + 7)

while True:
	try:
		n, m, k = map(int, input().split())
		a = list(map(int, input().split()))
		f = [[0] * (m + 1) for _ in range(n + 1)]
		p, d = [0] * n, [-1] * (k + 1)
		for i, x in enumerate(a): p[i] = d[x]; d[x] = i
		for i in range(n + 1): f[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD
				if p[i - 1] >= 0 and i - 1 - p[i - 1] <= j:
					f[i][j] = (f[i][j] - f[p[i - 1]][j - (i - 1 - p[i - 1])] + MOD) % MOD
		print(f[n][m])
	except:
		break

C++14(g++5.4) 解法, 执行用时: 545ms, 内存消耗: 9088K, 提交时间: 2019-04-19 16:27:29

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int mod=1e9+7;
int t,n,m,k;
int a[MAXN],dp[15][MAXN],ans[MAXN];
int main(){
	while(scanf("%d %d %d",&n,&m,&k)!=EOF){
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		memset(ans,0,sizeof(ans));
		memset(dp,0,sizeof(dp));
		ans[0]=1;
		for(int i=1;i<=n;i++){
			for(int j=i;j>=max(1,i-m);j--){
				ans[j]=((ans[j]+ans[j-1])%mod-dp[a[i]][j])%mod;
				dp[a[i]][j]=ans[j-1];
			}
		}
		cout<<(ans[n-m]+mod)%mod<<"\n";
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1632ms, 内存消耗: 13304K, 提交时间: 2018-08-29 14:23:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=1e9+7;
int A[N];
ll ans[N],DP[N][15];
int main(){
	int n,m,k;
	while(~scanf("%d%d%d", &n, &m, &k)){
		memset(DP,0,sizeof DP);
		memset(ans,0,sizeof DP);
		ans[0]=1;
		for(int i=1;i<=n;++i) scanf("%d",&A[i]);
		for(int i=1;i<=n;++i){
			for(int j=i;j>=max(i-m,1);--j){
				ans[j]+=(ans[j-1]-DP[j][A[i]])%M;
				DP[j][A[i]]=ans[j-1];
			}
		}
		printf("%lld\n", (ans[n-m]%M + M) % M);
	}
}