2021牛客寒假算法基础集训营1 A.串

题目链接

题目描述

长度不超过 $n$，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对 $10^9+7$ 取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。

例如，”unoacscc” 包含子序列 “us”，但 “scscucu” 则不包含子序列 “us”

输入描述:

一个正整数 $n（2 \leq n \leq 10^6）$

输出描述:

一个正整数，为满足条件的字符串数量对 $10^9+7$ 取模的值

示例1

输入

2

输出

1

示例2

输入

3

输出

77

示例3

输入

874520

输出

16471619

排列组合题~
我们考虑长度为 $n$ 的字符串的排列：

$$\underbrace{X,X,\cdots,X}_n$$

假设某一位置 $pos$ (本题下标默认从 $1$ 开始) 放上字母 $u$，如下：

$$\underbrace{X,X,X,u,\cdots,X,X}_n$$

显然后面字母 $s$ 的放法有 $n-pos$ 种，这 $n-pos$ 个位置为避免出现重复答案在放完 $s$ 后其他位置只能放除 $s$ 外的 $25$ 个字母，即每一种 $s$ 的摆放答案就是 $25^{n-pos-1}$ 种，一共 $(n-pos)*25^{n-pos-1}$ 种~
下面考虑 $pos$ 位置之前的字母放置方案，显然前面的位置可以放任意字母，答案就是 $26^{pos-1}$ 种~
综上所述，只需要遍历每一个位置求和即可得到答案：

$$ans=\sum_{i=1}^{n-1}26^{i-1}*(n-i)*25^{n-i-1}$$

但是题目要求所有长度小于等于 $n$ 的答案，所以有两种方案：

1. 化简上面的公式
2. 构造递推式，我采取了这种方法，根据上述公式得到如下递推式： $$\begin{cases} f_2=1\\ f_n=n*25^{n-1}+26*f_{n-1},n>2 \end{cases}$$

推导过程：

$f{n+1}=\sum{i=1}^{n}26^{i-1}(n+1-i)25^{n-i}$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+[26(n-1)25^{n-2}+26^2(n-2)*25^{n-3}+\cdots+26^{n-1}]$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+\sum_{i=1}^{n-1}26^{i}(n-i)*25^{n-i-1}$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+26\sum_{i=1}^{n-1}26^{i-1}(n-i)25^{n-i-1}$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+26f_n$

</font>
预处理算出 1e6 内的答案即可，AC代码如下：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

ll power(ll a, ll b) { return b ? power(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }

int main() {
    ll n;
    cin >> n;
    vector<ll> ans;
    ans.push_back(1);
    for (ll i = 2; i <= 1000000; i++) {
        ll sum = (power(25, i - 1) * i % mod + ans[i - 2] * 26 % mod) % mod;
        ans.push_back(sum);
    }
    for (int i = 1; i < ans.size(); i++) ans[i] = (ans[i - 1] + ans[i]) % mod;
    cout << ans[n - 2];
    return 0;
}