原题要求去掉m个元素后不同的子序列个数,可转化为求,长度为n-m的不同的子序列的个数。
dp[i][j]表示以数字i结尾的长度为j的子序列个数,ans[j]表示长度为j的子序列个数。
枚举序列,因为只要求ans[n-m],假设当前是第i个数字,那么更新时只需要更新[i-m,i]即可,
因为更小的长度的子序列不可能形成n-m长度的子序列。
然后,通过dp数组和ans数组的更新,保证不重复计数。
代码:
#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;
}