题意
给你一个大小为n的数组，你可以删掉数组中的任意m个数，问你在删除m个数之后剩下的数组有多少种。（其中数组的每个数的大小<=k）
分析
显然需要动态规划，而k又很小，所以二维dp没问题。
设dp[i][j]为前 i 位数中已经删除了j个数的方案数。现在考虑往后转移，假设此时接上来的是数字c，那么此时转移到dp[nxt[i][c]][j+nxt[i][c]-i+1]这个状态。其中nxt[i][c]表示i位置后第一次出现c的位置，因此需要删去的数的个数为nxt[i][c]-i+1。则dp[nxt[i][c]][j+nxt[i][c]-i+1]+=dp[i][j]。求nxt[i][c]时逆序求即可。最后答案是dp[n-i][m-i](0<=i<=m),末尾i个删去就符合删去m个的要求了。
#include <bits/stdc++.h>
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define FIN freopen("in.txt","r",stdin)
#define fuck(x) cout<<"["<<x<<"]"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int MAXN=1e5+;
const ll mod=1e9+; int n,m,k;
int a[MAXN],nxt[MAXN][];
ll dp[MAXN][]; int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=k;i++) nxt[n][i]=n+;
for(int i=n;i>=;i--){
for(int j=;j<=k;j++) nxt[i-][j]=nxt[i][j];
nxt[i-][a[i]]=i;
}
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<n;i++){
for(int j=;j<=m;j++){
for(int l=;l<=k;l++){
int n1=nxt[i][l],n2=n1-i-;
if(n2+j<=m)
dp[n1][j+n2]=(dp[n1][j+n2]+dp[i][j])%mod;
}
}
}
ll ans=;
for(int j=;j<=m;j++)
ans=(ans+dp[n-j][m-j]+mod)%mod;
printf("%lld\n",ans);
}
return ;
}