牛客——子序列（组合数学）

子序列

题目描述

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

输入描述:

第一行一个字符串 T T T
第二行一个正整数 m m m

输出描述:

输出答案对 1 0 9 + 7 10^9+7 109+7取模的值

示例1

输入

a
2

输出

51

说明

长度为2的里面有 a a a的串有51种

备注:

1 < = ∣ T ∣ , m < = 1 0 5 1<=|T|,m<=10^5 1<=∣T∣,m<=105

解决思路：

提示：以下的题解中， n n n为输入中的 m m m，即需要构造的字符串 S S S的长度， m m m为字符串 T T T的长度。

已知：求子串为 T T T且长度为 n n n的字符串的方案数。
求解：枚举 T T T的最后一个字母在 S S S中的所在位置，不难发现，位置的范围为： [ m , n ] [m,n] [m,n]。
乘法原理考虑当前位置的前后方案数。
前：在前 i − 1 i-1 i−1个位置中挑出 m − 1 m-1 m−1个位置放 T T T的前 m − 1 m-1 m−1个字符，在剩下的 i − m i-m i−m个位置中放除了 T T T的最后一个字符的字符（25种可能），贡献为 C ( i − 1 , m − 1 ) ∗ 2 5 i − m C(i-1,m-1)*25^{i-m} C(i−1,m−1)∗25i−m。
后：由于字符串 S S S中已经存在了子串 T T T，所以这些位置可以任意选择 26 26 26个字母，贡献为 2 6 n − i 26^{n-i} 26n−i。
前后的贡献相乘并求和即可。
证明：

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

ll fac[N];
ll ifac[N];

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
void init(const int n) {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    for (int i = 1; i <= n; i++) {
        ifac[i] = qpow(fac[i], mod - 2, mod);
    }
}
ll C(int n, int m) {
    if (n == 0 || m == 0 || n == m) return 1;
    ll up = fac[n];
    ll down = ifac[m] * ifac[n - m] % mod;
    return up * down % mod;
}

int main() {
    
    init(1e5);
    
    string s; cin >> s;
    int n; cin >> n;
    int m = s.size();
    
    ll ans = 0;
    for (int i = m; i <= n; i++) {
        ll t = C(i - 1, m - 1) * qpow(25, i - m, mod) % mod;
        t = t * qpow(26, n - i, mod) % mod;
        ans = (ans + t) % mod;
    }
    
    cout << ans << endl;
    return 0;
}