【每日一题】Removal (dp+思维 / 子序列 计数)

Solution
题意：给出n个元素，每个元素不大于k，求 删除m个元素后的子序列个数。

子序列问题，通常可以联想到dp来做，
考虑 维护 前 i 个元素删除 j 个元素的方案数，
考虑第 i 个元素删或者不删，即有：

但是这样计算的话肯定会有重复的方案，
拿样例2来说：
4 2 2
1 2 1 2
删除第一个元素和删除第二个元素 得到 1 2
删除第三个元素和删除第四个元素 得到 1 2
删除第二个元素和删除第三个元素 也得到 1 2
这样就重复了。

如何计算重复的子序列？
就像求路径一样，如果经过同一个点两次可以说明这条路已经走过了。
那么如果 a[i]在 i 之前出现过，设距离 i 最近的一个下标为x，
就有 a[x]+ i 之后某个序列 = a[i] + i 之后某个序列
重复的方案为 以 x 为右区间的且 x 不删除 且 删除 j-(i-x) 个元素 的方案数
即：
而当如果 i-x 之间的数比 j 大，就不会出现重复的情况
所以考虑用 last[i] 维护上一个 a[i] 出现的位置，也就是上文的x，枚举的时候判断然后减去重复的方案即可:

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=1e5+5;

ll dp[manx][20],a[manx],last[manx];
map<ll,ll>vis;

int main(){
    ll n,m,k;
    io;
    while(cin>>n>>m>>k){
        for(int i=1;i<=n;i++) cin>>a[i],last[i]=vis[a[i]],vis[a[i]]=i;
        for(int i=0;i<=n;i++) 
            if(i<m) dp[i][0]=dp[i][i]=1;
            else dp[i][0]=dp[i][m]=1;
        for(int i=1;i<=n;i++){
            ll k=min(i-1ll,m);
            for(int j=1;j<=k;j++){
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                dp[i][j]%=mod;
                if(last[i]&&j>=i-last[i])
                    dp[i][j]-=dp[last[i]-1][j-(i-last[i])];
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
        }
        cout<<dp[n][m]<<endl;
        for(int i=1;i<=n;i++) last[i]=0;  vis.clear();
    }
    return 0;
}