题目描述

​ 给定一个小写字母字符串T

​ 求有多少长度为mm的小写字母字符串S满足，T是S的一个**子序列 **(不需要连续)

分析

  • 我们从合法的新串下手，考虑制定出一种方法来从中找出原串。

  • 对这种方法的要求是：按照这种方法 找出的新串 的下标 必须唯一。

  • 一种合理的匹配方式是：

    ​ 一种匹配方式

  • 我们知道，由子序列 S 构造原序列 T，问方案数这类问题，就是要保证
  • 如果你在 T 确定 T 的第 ii个字符 tit_i，匹配的是 S 中的第 p个字符 sps_p，
  • 并且你在 T 确定 T的第 jj个字符 tjt_j，匹配的是 S 中的第 p+1个字符 sp+1s_{p+1}，
  • 除了 ti = sp,tj=sp+1t_i \ = \ s_p,t_j = s_{p+1}以外，还要保证，ti+1...tj−1t_{i+1}...t_{j-1} 的所有字符，都不包含 tit_i。
  • 现在考虑按照这种匹配思路，从原串开始，构造新串。

如果范围不大可以 dpdp 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    dp[0][0] = 1;
    for (int i=1; i<=m; i++)    //从你决定开始匹配原串第一个字符之前，放什么都行，每一个位置有26种放法。
    {
        dp[i][0] = dp[i-1][0] * 26 % MOD;
    }
     
    for (int i=1; i<=m; i++)//枚举新串
    {
        for (int j=1; j<=min(i, n); j++)//枚举原串
        {
            //对于新串的第 i 个字符，有两种情况：
            //一种是第i个字符匹配上原串的第j个字符
            //一种是第i个字符在前i-1个已经匹配上原串的第j个字符的情况下，有25种放法。
            dp[i][j] += dp[i-1][j-1] + dp[i-1][j] * 25 % MOD, dp[i][j] %= MOD;
        }
    }
    printf("%lld\n",dp[m][n]);
}

数据范围大

  • 还是利用排列组合公式，先确定原字符串 T 中每个字母的位置，再确定剩下的空位放什么。
  • 然后，我们不妨规定：对于一个空缺的位置，不允许放位于它左边的第一个已经安放好的字母，其它字母随便放。
  • 对于某一个字母的周围出现和这个字母一样的字母的情况，这种做法能控制 重复的字母一定位于它的左边。
  • 我们还发现。如果原串第一个字母被安放到了位置 p，那么位置区间 [1,p) 所有字母都能放，其它空位只能放 25 种。
  • 枚举第一个字母的位置，再利用组合数安放剩下的字母。接下来的操作见上一条。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6+10;
const int mod = 1e9+7;

int fac[N << 1],invfac[N << 1];
int C(int n,int m)
{
    return n < m ? 0 : (long long)fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
void init()
{
	// i最大值为数据量
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=2e6 + 10;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=2e6 + 10;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=2e6 + 10;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
}


int qmi(int a,int b){
    int res = 1;
    a %= mod;
    while(b){
        if(b&1) res = res * a % mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}

signed main()
{
    string s;cin>>s;
    int n;cin>>n;
    int res = 0;
    int len = s.size();
    init();
    for(int i = 1;i <= n-len+1;i++){
        res = (res + qmi(26,i-1)*C(n-i,len-1)%mod*qmi(25,n-i-len+1))%mod;
    }
    cout << res << endl;
    return 0;
}

文章转自