思路一

设 $i$ 为字符串长度， $c[i]$ 是不含 $u$ 的字符串数， $b[i]$ 是含 $u$ 但不含 $us$ 的字符串数， $a[i]$ 是 $i$ 时的答案： $c[i]=c[i-1]\times25\quad(每格可以放除u外的任意字符，含s)$

$b[i]=b[i-1]\times25+c[i-1]\quad(最新一格放非s+放u的情况)$

$a[i]=a[i-1]\times26+b[i-1]\quad((之前有us)最新一格随便放或(之前无us)放s)$

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
#define mn 1000010
ll n, c[mn], b[mn], a[mn], mod = 1e9 + 7, ans;
signed main()
{
    sc(n);
    c[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        c[i] = c[i - 1] * 25 % mod;

        b[i] = (b[i - 1] * 25 + c[i - 1]) % mod;
        //如果已经有u,那不能放s(*25); 如果还没有u,要放一个u来满足定义

        a[i] = (a[i - 1] * 26 + b[i - 1]) % mod;
        //如果已经有us,那随便放(*26); 如果还没有,就放s跟之前的u凑一个us

        ans = (ans + a[i]) % mod;
    }
    printf("%lld", ans);
    return 0;
}

可以压缩数组，代码如下：

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long newu,nou=1,t,n,r;
signed main()
{
    scanf("%lld",&n);
    if(n<=1) return printf("0")&0;
    for(int i=0;i<n;++i)
    {
        t=(t*26+newu)%mod;
        (r+=t)%=mod;
        newu=(newu*25+nou)%mod;
        nou=nou*25%mod;
    }
    return printf("%lld",r)&0;
}

思路二

设 $dp[i]$ 表示长为 $i$ 的含子序列 us 的串的数目

递推方程： $dp[i]=dp[i-1]\times26+26^{i-1}-dp[i-1]-25^{i-1}$ 解释：

$dp[i-1]\times26$ 是说如果长为 $i-1$ 的有 us 的话，第 $i$ 位随便放啥都行
26^{i-1}-dp[i-1]-25^{i-1}
- $26^{i-1}$ 是长 $i-1$ 的串的全集
- $26^{i-1}-dp[i-1]$ 是长 $i-1$ 的一个子序列 us 也没有的串
- $25^{i-1}$ 是说一个 u 也没有的长 $i-1$ 的串的全集
- 综合起来看， $26^{i-1}-dp[i-1]-25^{i-1}$ 说的是所有含 u 但不含 us 的全体字符串
- 在这个条件下，为使得长为 $i$ 的串有子序列 us ，第 $i$ 位只能放字符 s

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
#define mn 1000010
ll n, dp[mn], pow25[mn], pow26[mn], mod = 1e9 + 7, ans;
signed main()
{
    sc(n);
    pow25[0] = 1, pow26[0] = 1;
    for (ll i = 1; i <= n; ++i)
    { //注意减法取模
        pow25[i] = (pow25[i - 1] * 25) % mod;
        pow26[i] = (pow26[i - 1] * 26) % mod;
        dp[i] = (dp[i - 1] * 26 + pow26[i - 1] - dp[i - 1] - pow25[i - 1] + 2 * mod) % mod;
        ans = (ans + dp[i]) % mod;
    }
    printf("%lld", ans);
    return 0;
} //可以压缩数组到空间复杂度O(1),很简单,可以自行尝试

lr580 发表于 2年前

//这个公式渲染也太难看了 QwQ

Tension 发表于 1年前

警示后人

借楼，题目里是字符串长度不超过 $n$ ,不是长度等于 $n$ ，千万不要跟我一样眼瞎（

Tension 发表于 1年前

lr580 一年前写的一年前的学习笔记，等于两年前的笔记orz

两种DP思路

思路一

思路二

警示后人