update:添加了个优化

又是一道简单dp,qwq

我们读题，发现k和m的范围都很小，所以我们考虑从这里入手

我们设dp[i][j]表示选了i个数，最后一个是j的方案数，那么就有：

那么，我们想下转移。

首先，我们枚举新增了一个数a[i]

那么，分为两种情况:

一.a[i]被剔除了

这个情况下，相当于我们没有新增a[i]，所以所有的dp的值都不变，不做任何操作即可

二.a[i]没被剔除

那么，我们按方程，难到要枚举前面选了几个数嘛？

不,我们直接枚举前面剔除多少个数，这样，如果我们枚举出前面剔除了几个数后，我们就知道现在序列中有几个数了。

然后，我们再枚举序列末尾是哪个数即可

但是，如果我们这么写转移:

连样例都过不了

为什么？

因为，我们其实之前的时候可能已经算了长度为i，末尾为a[i]的序列个数了，但，我们现在又新增了一个a[i]后，就可能将某些序列重复计算了

举个例子:

1 2 3 3

我们在i=3的时候，算了一遍1 2 3这个序列了

但i=4时，我们如果向上面那么转移的话，就会再算一遍1 2 3这个序列，只是结尾的3来自不同的a[i]而已。

那么，怎么办呢？

很简单，既然我们会重复计算，我们不加就好了！

因为，我们现在的长度为i-j,以a[i]结尾的序列中，一定包含了以前出现过的，长度为i-j,以a[i]结尾的序列，所以，我们直接将转移方程改成

当然，为了防止后效性，我们的j要从小到大枚举。

另外，当i<=j时，我们就要停止计算了(不然i-j-1就小于0了)

但是，这样的话，当i=j的时候，我们的值就会漏算，而漏算了这个后就会导致i-j=1的时候答案为0

怎么办呢？当i-j=1的时候，明显只有一个方案，所以，我们在每次算完后再令dp[1][a[i]]=1即可

复杂度:

Ps:我这么设方程相当于滚动了一维数组，如果不想想那么多，可以直接设方程:

表示前i个数中，剔除了j个，最后是k的序列的方案数，直接类似的转移即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,mod=1e9+7;
int a[N];
int dp[N][11];
int main(){
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof(dp));//清零
        dp[1][a[1]]=1;
        for(int i=2;i<=n;++i){
            for(int j=0;j<=m;++j){
                if(i==j){
                    break;
                }
                int res=0;
                for(int p=1;p<=k;++p){
                    res=(res+dp[i-j-1][p])%mod;
                }
                dp[i-j][a[i]]=res;
            }
            dp[1][a[i]]=1;
        }
        int ans=0;
        for(int i=1;i<=k;++i){
            ans=(ans+dp[n-m][i])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

新增：

看了下转移方程，然后发现，后面这部分，可以使用前缀和来优化一下，所以，我们可以直接令，那么，转移就直接变成了

复杂度:[但是好像跑得更慢了？？？人丑自带大常数qwq]

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1,mod=1e9+7;
int a[N];
int dp[N][11];
int s[N];
signed main(){
    int n,m,k;
    while(~scanf("%lld%lld%lld",&n,&m,&k)){
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
        }
        memset(dp,0,sizeof(dp));
        memset(s,0,sizeof(s));
        dp[1][a[1]]=s[1]=1;
        for(int i=2;i<=n;++i){
            for(int j=0;j<=m;++j){
                if(i==j){
                    break;
                }
                s[i-j]-=dp[i-j][a[i]];
                dp[i-j][a[i]]=s[i-j-1];
                s[i-j]+=dp[i-j][a[i]];
                s[i-j]%=mod;
            }
            s[1]+=(dp[1][a[i]]==0);
            dp[1][a[i]]=1;
        }
        s[n-m]=(s[n-m]+mod)%mod;
        printf("%lld\n",s[n-m]);
    }
    return 0;
}