NC17137 Removal

原题地址：

https://ac.nowcoder.com/acm/problem/17137

数据没锅,是我的锅orz,谢谢邓老师帮我找bug

基本思路：

这题的本质是一个挺简单的计数dp，和这道题其实比较像https://ac.nowcoder.com/acm/contest/4853/C 我们看m比较小所以只要将前i个里取j个变换成前i个里j个不取就行了。
我们设dp[i][j]表示前i个数中j个不取,那么不考虑重复的情况我们可以考虑这样的转移方程：
$图片说明$ 即在第i个位置取或不取的情况。
那么考虑去重，去重的方法其实和上面那题思路完全一样，对于每个位置a[i]我们直接减去a[i]上一次出现的位置结尾的所有长度相同的子序列，只是对于找长度相同我们做一个转换，前i个里j个不取的子序列的长度即为(i - j)，长度相同转化为在上一个位置要几个不取即是解这样一个方程 $图片说明$ 那么得到去重的转移方程 $图片说明$ ;根据上面两个转移方程就能成功得到答案了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

const int maxn = 1e5 + 50;
const int mod = (int)1e9 + 7;
int n,m,k,a[maxn];
int last[15],dp[maxn][15];//前i个数中j个不取;
signed main() {
  while(cin >> n >> m >> k){
    mset(last,-1);
    mset(dp,0);
    rep(i,1,n) cin >> a[i];
    rep(i,1,10) dp[i][i] = 1;
    rep(i,0,n) dp[i][0] = 1;
    rep(i,1,n){
      rep(j,1,min(i-1,m)){
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;
        int num = last[a[i]] + j - i;//算出长度相等等同于几个不取;
        if(last[a[i]] != -1 && num >= 0) dp[i][j] = (dp[i][j] - dp[last[a[i]] - 1][num] + mod) % mod;
      }
      last[a[i]] = i;//更新这个数字上次出现的位置;
    }
    cout << dp[n][m] << endl;
  }
  return 0;
}