周中训练 DAY1

· · 个人记录

题意

给一个长度是n的仅含有小写字母的字符串s,求s 的不同非空子序列一共有多少个，答案对1e9+7取模

下面给出子序列定义：

字符串的 子序列 是经由原字符串删除k个（k有可能等于0）字符但不改变剩余字符相对位置的一个新字符串。

1<=n<=2000

原思路

肯定有比我更容易的想法。

我认为硬做不好，所以反过来想，直接对子序列进行讨论。

那么考虑 f_{i,j} 表示一个长为 i 的子序列中，结尾元素对应在原串下标为 j 的位置时的方案数。

（我也是尝试多次后才有这样的状态定义的）

那么考虑将 f_{i,j} 拓展至 f_{i+1,k}，为了保证不重，需满足 k 是 s[j+1,n] 这段区间中，第一个出现的。也就是说 k 后面不存在 s_q=s_k。

那么就能发现，这样转移不会漏解，因为 k 是第一出现的，显然也不会多解。

这而判断 k 是否合法这一步可以通过预处理完成，很简单吧。

（我是定义 p_{i,j} 表示 s[i,n] 这段区间中 j 元素第一次出现的位置，就有 k=p_{j+1,c}）

现思路

完全没必要设 长度 这一维啊！

直接令 f_i 表示以 s_i 结尾时的方案数即可。

从 我为人人 的角度看，令 f_i 转移至 f_j，那么这个 j=p_{i+1,c}，枚举 c 即可。

归根结底，还是思维有所固化所导致的。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e3+5,mod=1e9+7;
int n,f[N]={1},p[N][30],ans;
string s;

signed main(){
    cin>>s; n=s.size(); s=" "+s;
    for(int i=n; i>=1;i--){
        for(int j=0; j<26;j++) p[i][j]=p[i+1][j];
        p[i][s[i]-'a']=i;
    }
    for(int i=0; i<n;i++){
        for(int j=0; j<26;j++) 
         if(p[i+1][j]) f[p[i+1][j]]=(f[p[i+1][j]]+f[i])%mod;
        ans=(ans+f[i])%mod;
    }
    cout<<(ans+f[n]-1)%mod;
    return 0;
}