Removal

题目大意：
给定一个 个数字的序列，序列中的数字在 中，从序列中删去 个数字，问能得到多少种不同的序列。

解题思路（from ftiasch）：

把问题转换成考虑有多少种方案可以构成一个有 个数字的序列，而且这个序列是由给定的原数字序列删掉 个数字而得到的。

设 ，其中 代表当前遍历到的数字序列的下标， 代表当前已经删掉的数字个数， 代表当前已经构造完毕的数字序列的最后一个数字。

对于这个 ，我们只需要遍历原数字序列的每一个数字（其实就是把 数组由 推到 ），然后对于满足  的 ，考虑不把当前遍历到的数字放进去（其实就相当于删除掉当前遍历到的数字），进行如下转移：

不难发现，对于每一次从 到 的转移， 前面的信息其实都是没用的，所以我们可以只用一个 来保存 中的信息，用 来记录更新出来的 。每次更新完后再将 中的信息放入 中即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int MAXN=1e5+5;

int dp[15][15],new_dp[15][15];
int s[MAXN];
int main(){
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i]);
        dp[0][0]=1;
        for(int index=1;index<=n;index++){
            memset(new_dp,0,sizeof(new_dp));
            for(int delet=0;delet<=m;delet++){
                for(int now=0;now<=k;now++){
                    if(delet<m&&now!=s[index])
                        new_dp[delet+1][now]=(new_dp[delet+1][now]+dp[delet][now])%MOD;
                    new_dp[delet][s[index]]=(new_dp[delet][s[index]]+dp[delet][now])%MOD;
                }
            }
            for(int delet=0;delet<=m;delet++){
                for(int now=0;now<=k;now++)
                    dp[delet][now]=new_dp[delet][now];
            }
        }
        int ans=0;
        for(int i=0;i<=k;i++)
            ans+=dp[m][i],ans%=MOD;
        printf("%d\n",ans);
    }
    return 0;
}