题解 | 串

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

const int MOD = 1000000007;

int solve(int n) {
    // dp[i][j] 表示长度为i时的状态j
    vector<vector<long long>> dp(n + 1, vector<long long>(3, 0));
    
    // 初始化长度为1的情况
    dp[1][0] = 25;  // 除了u的所有字母
    dp[1][1] = 1;   // 只有u
    dp[1][2] = 0;   // 不可能出现us
    
    // 对每个长度进行转移
    for (int i = 2; i <= n; i++) {
        // 1. 还未出现u
        dp[i][0] = (dp[i-1][0] * 25) % MOD;
        
        // 2. 已出现u，未出现s
        dp[i][1] = (dp[i-1][0] + dp[i-1][1] * 25) % MOD;
        
        // 3. 已出现us
        dp[i][2] = (dp[i-1][1] + dp[i-1][2] * 26) % MOD;
    }
    
    // 返回所有长度的us状态之和
    long long result = 0;
    for (int i = 2; i <= n; i++) {
        result = (result + dp[i][2]) % MOD;
    }
    
    return result;
}

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

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;
    
    static int solve(int n) {
        // dp[i][j] 表示长度为i时的状态j
        long[][] dp = new long[n + 1][3];
        
        // 初始化长度为1的情况
        dp[1][0] = 25;  // 除了u的所有字母
        dp[1][1] = 1;   // 只有u
        dp[1][2] = 0;   // 不可能出现us
        
        // 对每个长度进行转移
        for (int i = 2; i <= n; i++) {
            // 1. 还未出现u
            dp[i][0] = (dp[i-1][0] * 25) % MOD;
            
            // 2. 已出现u，未出现s
            dp[i][1] = (dp[i-1][0] + dp[i-1][1] * 25) % MOD;
            
            // 3. 已出现us
            dp[i][2] = (dp[i-1][1] + dp[i-1][2] * 26) % MOD;
        }
        
        // 返回所有长度的us状态之和
        long result = 0;
        for (int i = 2; i <= n; i++) {
            result = (result + dp[i][2]) % MOD;
        }
        
        return (int)result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solve(n));
        sc.close();
    }
}

def solve(n):
    MOD = 10**9 + 7
    
    # dp[i][j] 表示长度为i时:
    # j=0: 还未出现u
    # j=1: 已经出现u，还未出现s
    # j=2: 已经出现us
    dp = [[0] * 3 for _ in range(n + 1)]
    
    # 初始化长度为1的情况
    dp[1][0] = 25  # 除了u的所有字母
    dp[1][1] = 1   # 只有u
    dp[1][2] = 0   # 不可能出现us
    
    # 对每个长度进行转移
    for i in range(2, n + 1):
        # 1. 还未出现u：前一个状态是未出现u，新字母不是u
        dp[i][0] = (dp[i-1][0] * 25) % MOD
        
        # 2. 已出现u，未出现s：
        # - 前一个状态未出现u，这个位置是u
        # - 前一个状态已出现u但未出现s，新字母不是s
        dp[i][1] = (dp[i-1][0] + dp[i-1][1] * 25) % MOD
        
        # 3. 已出现us：
        # - 前一个状态已出现u未出现s，这个位置是s
        # - 前一个状态已出现us，新加任何字母都行
        dp[i][2] = (dp[i-1][1] + dp[i-1][2] * 26) % MOD
    
    # 返回所有长度的us状态之和
    result = 0
    for i in range(2, n + 1):
        result = (result + dp[i][2]) % MOD
    
    return result

# 读取输入
n = int(input())
# 输出结果
print(solve(n))