Question

一串由组成的长度为的序列，求拿掉m个数后有多少个不相同的子序列。(mod 1e9+7)

Solution

这道题去重和DP的思路和操作集锦是差不多的。
唯一不同的点是操作集锦那道题中的表示的是选了多少个，这里是不选多少个，因为的范围比较小，如果表示选了多少个这里会MLE+TLE。
再来回顾一下吧。
设表示前个数中不选个位置的方案数。
我们先考虑不去重的情况，易得:表示选和不选第个数的情况。
接下来就是本题的难点如何去重了？
eg:1 2 4 3 4
重复的情况会出现在:[1 4], [2 4], [1 2 4]。当且仅当中间的4和3都去掉的时候会发生这种情况。
考虑容斥:两个序列相同的情况，重复的数量为所在的位置的序列和处于和位置的序列可以构成一样的序列。且和之间的数是不可以取的。
也就是说如果之前已经出现了一次那么一定会有重复的部分，那我们就需要去重了，

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 +5;

int n,m,k,s[N];
ll f[N][15],pos[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>m>>k){
        memset(f,0,sizeof(f));
        memset(pos,0,sizeof(pos));
        for(int i=1;i<=n ;i++) cin>>s[i];
        for(int i=1;i<=10;i++) f[i][i]=1;
        for(int i=0;i<=n ;i++) f[i][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=min(i-1,m);j++){
                f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
                if(pos[s[i]]>=0 && i-pos[s[i]]<=j) f[i][j]=(f[i][j]-f[pos[s[i]]-1][j-(i-pos[s[i]])]+mod)%mod;
            }
            pos[s[i]]=i;
        }
        cout<<f[n][m]<<'\n';
    }
    return 0;
}