当前位置：首页 > news >正文

小红的漂亮串(C++ DP 取模运算)

news 来源：原创 2024/5/3 5:02:22

题目描述

小红定义“漂亮串”为：至少有两个“red”子串。
n 个字符的字符串(只有小写字母)，一共有多少种漂亮串，结果对 $1 e 9 + 7$ 取模。

分析

“至少”两个,那就总的，把 0 个”red”，和 1 个“red”减去就是我们想要的结果，

也可以直接用排列组合，数学公式算结果，但是会溢出，因为有阶乘，高次幂和除法取模，答案总是差一些，就是要给你设限制。

维护两个DP数组：
A[i]表示长度 $i$ 的字符串中一个red也没有的种类数；
B[i]表示长度 $i$ 的字符串中有且只有一个red的种类数；

对于A[i]：

不选字符d，即没有构成一个新red的可能，除了d还有25个字母，那么A[i] = A[i-1]*25。
选字符串d，即有构成red的可能，它的前两个字符就不能是re，否则不符合“一个red也没有”。所以此时A[i] = A[i-1] -A[i-3]。
综上， $A [i] = A [i - 1] * 26 - A [i - 3]$ 。

对于B[i]：

不选字符d，B[i] = B[i-1]*25
选字符d：
- 若之前一个red也没有，且前两个字符为re，那就正好有一个red，B[i] = A[i-3]
- 若之前已经有一个red，那他的前两个字符不能是re。B[i] = B[i-1] - B[i-3]
综上， $B [i] = B [i - 1] * 26 - B [i - 3] + A [i - 3]$

递推公式：

$ans(n)=26^n-A[n]-B[n]$

然后就是按照DP问题的解法，以上部分完成了：

DP数组的含义
递推公式

至于遍历顺序和初始化，比较简单，请直接看代码。

#include <iostream>
#include <vector>

#define MOD 1000000007
typedef long long ll;

using namespace std;

ll beautifulString(int n){
    ll ans = 26 * 26;

    vector<ll> A(n + 1), B(n + 1); // DP数组的含义 和 初始化很重要, 请注意
    A[0] = 1; A[1] = 26; A[2] = 26 * 26;
    B[0] = 0; B[1] = 0; B[2] = 0;

    for(int i = 3; i <= n; i++) { // 遍历顺序
        // 递推公式
        A[i] = (A[i - 1] * 26 % MOD - A[i - 3] % MOD) % MOD;
        B[i] = (B[i - 1] * 26 % MOD + (A[i - 3] - B[i - 3]) % MOD) % MOD;
        ans = (ans * 26) % MOD;
    }

    ans = (ans - (A[n] + B[n]) % MOD) % MOD;

    return ans;
}

int main(){
    int n;
    cin >> n; 
    cout << beautifulString(n);
    return 0;
}