关于#字符串#的问题，如何解决？

Question

D2jo8. 基因计数（加强版）
时间限制：1.0s   内存限制：256.0MB   代码提交间隔：5分钟(现在可以提交)  

问题描述
　　给定一个碱基序列，问长度为L的包含这段碱基序列的基因有多少种？注意基因只由A、T、G、C四种碱基组成，如果表达出来不同，则认为是不同的基因。
输入格式
　　输入的第一行包含一个字符串，表示给定的碱基序列。
　　第二行包含一个整数L。
输出格式
　　输出一个整数，表示答案对123456789取余的结果。
样例输入  
ATAT
6
样例输出  
47
数据规模和约定
　　对于10%的评测用例，1 ≤ 字符串长度 ≤ 10， 1 ≤ L ≤ 10。
　　对于20%的评测用例，1 ≤ 字符串长度 ≤ 10， 1 ≤ L ≤ 100。
　　对于50%的评测用例，1 ≤ 字符串长度 ≤ 100， 1 ≤ L ≤ 10000。
　　对于100%的评测用例，1 ≤ 字符串长度 ≤ 100， 1 ≤ L ≤ 10^18。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 105, MOD = 123456789;

int n, L;
int f[N][N][N][2];

int main()
{
    string s;
    cin >> s >> L;

    n = s.size();

    // 初始化 f 数组
    for (int i = 0; i < n; i ++ )
        f[i][i][0][0] = f[i][i][0][1] = 1;

    // 递推计算 f 数组
    for (int len = 1; len <= L; len ++ )
        for (int l = 0; l + len - 1 < n; l ++ )
        {
            int r = l + len - 1;
            for (int k = 0; k <= L; k ++ )
                for (int t = 0; t < 2; t ++ )
                {
                    // 如果当前位置可以选择 s[l]，则从左边转移
                    if (s[l] == 'A' && k || s[l] == 'T' && k < L)
                        f[l][r][k + (s[l] == 'A')][0] = (f[l][r][k + (s[l] == 'A')][0] + f[l + 1][r][k][t]) % MOD;
                    if (s[l] == 'G' && k || s[l] == 'C' && k < L)
                        f[l][r][k + (s[l] == 'G')][0] = (f[l][r][k + (s[l] == 'G')][0] + f[l + 1][r][k][t]) % MOD;

                    // 如果当前位置可以选择 s[r]，则从右边转移
                    if (s[r] == 'A' && k || s[r] == 'T' && k < L)
                        f[l][r][k + (s[r] == 'A')][t] = (f[l][r][k + (s[r] == 'A')][t] + f[l][r - 1][k][t]) % MOD;
                    if (s[r] == 'G' && k || s[r] == 'C' && k < L)
                        f[l][r][k + (s[r] == 'G')][t] = (f[l][r][k + (s[r] == 'G')][t] + f[l][r - 1][k][t]) % MOD;
                }
        }

    // 统计答案
    int res = 0;
    for (int i = 0; i <= L; i ++ )
        for (int j = 0; j < 2; j ++ )
            res = (res + f[0][n - 1][i][j]) % MOD;

    cout << res << endl;

    return 0;
}

帮帮我

Answer 1

望采纳

#include <iostream>
#include <cstring>
using namespace std;

const int N = 105, MOD = 123456789;

int n, L;
int f[N][N][N][2];

int main()
{
    string s;
    cin >> s >> L;

    n = s.size();

    // 初始化 f 数组
    for (int i = 0; i < n; i ++ )
        f[i][i][0][0] = f[i][i][0][1] = 1;

    // 递推计算 f 数组
    for (int len = 1; len <= L; len ++ )
        for (int l = 0; l + len - 1 < n; l ++ )
        {
            int r = l + len - 1;
            for (int k = 0; k <= L; k ++ )
                for (int t = 0; t < 2; t ++ )
                {
                    // 如果当前位置可以选择 s[l]，则从左边转移
                    if (s[l] == 'A' && k || s[l] == 'T' && k < L)
                        f[l][r][k + (s[l] == 'A')][0] = (f[l][r][k + (s[l] == 'A')][0] + f[l + 1][r][k][t]) % MOD;
                    if (s[l] == 'G' && k || s[l] == 'C' && k < L)
                        f[l][r][k + (s[l] == 'G')][0] = (f[l][r][k + (s[l] == 'G')][0] + f[l + 1][r][k][t]) % MOD;

                    // 如果当前位置可以选择 s[r]，则从右边转移
                    if (s[r] == 'A' && k || s[r] == 'T' && k < L)
                        f[l][r][k + (s[r] == 'A')][t] = (f[l][r][k + (s[r] == 'A')][t] + f[l][r - 1][k][t]) % MOD;
                    if (s[r] == 'G' && k || s[r] == 'C' && k < L)
                        f[l][r][k + (s[r] == 'G')][t] = (f[l][r][k + (s[r] == 'G')][t] + f[l][r - 1][k][t]) % MOD;
                }
        }

    // 统计答案
    int res = 0;
    for (int i = 0; i <= L; i ++ )
        for (int j = 0; j < 2; j ++ )
            res = (res + f[0][n - 1][i][j]) % MOD;

    cout << res << endl;

    return 0;
}