子序列计数

hwx12233 · 2021-08-13 11:23:23 · 个人记录

题目

给定一个长度为n 的字符串，串中的字符保证是前k 个小写字母。你可以在字符串后再添加m 个字符，使得新字符串所包含的不同的子序列数量尽量多。当然，前提是只能添加前k 个小写字母。求新的长度为n+m 的串最多的不同子序列 数量。答案对109 +7 取模。

输入

输入第一行两个数m，k。 接下来一行一个字符串，长度为n，表示原始的字符串。

1 3              8
ac 

我们首先要学会O(N)求子序列数量

暴力很明显是O(2^N)的

就是枚举每一位取还是不取

那么这也可以运用到dp中

设dp[i]表示i之前的（不重复）子序列数量

如果没有字符重复很明显递推式为

那么有重复时

在到第二个a时若按照此方法转移则会有重复

我们发现重复的是上一个a之前所有的子序列

因为上一个a之前的子序列加上a已经计算过一遍了

所以递推式改为

那么我们可以看出dp数组一定是递增的

那么我们考虑加上字符

我们要让结果最大那必然要让减去的最小

由于是dp递增的 所以我们每次加上的一定是pre最小的字符

故排序之后依次取就好了

#include<bits/stdc++.h>
using namespace std;
#define LBW return
#define AK 0
#define IOI ;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e6+10;
const int mod=1e9+7;
int n,m,k,ans,dp[N<<1],pre[40];char a[N];
struct node{int id,pre;}rankk[40];
inline bool cmp(node x,node y){return x.pre<y.pre;}
int main(){
    m=read(),k=read();
    cin>>a;n=strlen(a);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]*2%mod;
        if(pre[a[i-1]-'a'])dp[i]=(dp[i]-dp[pre[a[i-1]-'a']-1]+mod)%mod;
        pre[a[i-1]-'a']=i;
    }
    for(int i=0;i<k;i++)rankk[i]=(node){i,pre[i]};
    sort(rankk,rankk+k,cmp);
    int ord=0;
    for(int i=n+1;i<=n+m;i++){
        dp[i]=dp[i-1]*2%mod;
        if(pre[rankk[ord].id])dp[i]=(dp[i]-dp[pre[rankk[ord].id]-1]+mod)%mod;
        pre[rankk[ord].id]=i;ord=(ord+1)%k;
    }
    cout<<dp[n+m];
    LBW AK IOI
}