Removal

题意：求一个n长度的序列删除m个元素后不同序列的个数，结果对1000000007取模

思路：dp[i][j]为前i个元素删除j个元素序列的个数
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
去重：因为重复只存在于二个相同元素之间的元素全部删除后的在二个元素中删除其中一个
dp[i][j]=dp[i][j]-dp[k-1][j-(i-k)]
k是与该元素相同的上一个元素的下标

代码：

#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;

typedef long long ll;

int a[100005];
ll dp[100005][15];
int ma[100005];

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(ma,-1,sizeof(ma));
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1; i<=n; i++)
        {
            dp[i][0]=1;
            for(int j=1; j<=min(m,i); j++)
            {
                dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%inf;
                int p=ma[a[i]];
                if(p!=-1&&(i-p)<=j)
                {
                    dp[i][j]=(dp[i][j]-dp[p-1][j-(i-p)]+inf)%inf;
                }
            }
            ma[a[i]]=i;
        }
        printf("%lld\n",dp[n][m]);
    }
    return 0;
}