# 可爱串

整体思路，就含有子序列的字符串数量减去含有子串的字符串数量。

因为子序列数量已经是包含子串数量的。剩下的就是只有子序列且没有子串的字符串数量。

需要注意我们求的不是长度为 i 的字符串里有多少个 red 子序列。

而是可以有多少个长度为i 的字符串含有子序列 red

同理，可以有多少个长度为i的字符串含有 red 子串

认清这一点很重要！

# 求子串

dp2[i][3] 长度为i 且含有子串 red 的字符串数量有多少

dp2[i][2] 长度为i 且含有子串 re 的字符串数量有多少

dp2[i][1] 长度为 i 且含有子串 r 的字符串数量有多少

dp2[1][0] 长度为 i 且含有只有 de, ee , e, d的字符串的字符串数量有多少。

// 求子串
dp2[0][0] = 1;
for(int i = 1;i <= n; i++) {
    dp2[i][0] = (dp2[i - 1][2] + dp2[i - 1][1] + dp2[i - 1][0] * 2) % mod; // 含有 re 的可以把 r改成d， 含有r 的可以改成
    dp2[i][1] = (dp2[i - 1][2] + dp2[i - 1][1] + dp2[i - 1][0]) % mod;
    dp2[i][2] = (dp2[i - 1][1]);
    dp2[i][3] = (dp2[i - 1][3] * 3 + dp2[i - 1][2]) % mod;
}
``

### 求子序列 

dp1[i][3] 长度为i 且 含有子序列 red 的字符串数量 有多少 

dp2[i][2] 长度为i 且 含有子序列 re  的字符串数量有多少 

dp2[i][1] 长度为 i 且 含有子序列 r 的字符串数量有多少 

dp2[1][0] 长度为 i 且 含有 只含有 e 和 d 的字符串的字符串数量有多少。

```CPP 

// 求子序列
dp1[0][0]=1;
for(int i=1;i<=n;i++)
{
    dp1[i][0] = (dp1[i - 1][0] * 2) % mod;
    dp1[i][1] = (dp1[i - 1][0] + dp1[i - 1][1] * 2) % mod;
    dp1[i][2] = (dp1[i - 1][1] + dp1[i - 1][2] * 2) % mod;
    dp1[i][3] = (dp1[i - 1][2] + dp1[i - 1][3] * 3) % mod;
}

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


#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=1e9+7;

int main()
{
    int n;

    cin>>n;
    vector<vector<ll>> dp1(n + 1,vector<ll> (4,0));
    vector<vector<ll>> dp2(n + 1,vector<ll> (4,0));
    // 求子串
    dp2[0][0] = 1;
    for(int i = 1;i <= n; i++) {
        dp2[i][0] = (dp2[i - 1][2] + dp2[i - 1][1] + dp2[i - 1][0] * 2) % mod;
        dp2[i][1] = (dp2[i - 1][2] + dp2[i - 1][1] + dp2[i - 1][0]) % mod;
        dp2[i][2] = (dp2[i - 1][1]);
        dp2[i][3] = (dp2[i - 1][3] * 3 + dp2[i - 1][2]) % mod;
    }

    // 求子序列
    dp1[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp1[i][0] = (dp1[i - 1][0] * 2) % mod;
        dp1[i][1] = (dp1[i - 1][0] + dp1[i - 1][1] * 2) % mod;
        dp1[i][2] = (dp1[i - 1][1] + dp1[i - 1][2] * 2) % mod;
        dp1[i][3] = (dp1[i - 1][2] + dp1[i - 1][3] * 3) % mod;
    }

    cout<<(dp1[n][3] - dp2[n][3])%mod;

}

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