题解 | 串

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        final int MOD = 1000000007;

        long[] pow26 = new long[n + 1];
        pow26[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow26[i] = (pow26[i - 1] * 26) % MOD;
        }

        long sum = 0;
        long dp0 = 1; 
        long dp1 = 0; 

        for (int m = 1; m <= n; m++) {
            long newDp0 = (dp0 * 25) % MOD;
            long newDp1 = (dp0 * 1 + dp1 * 25) % MOD;

            if (m >= 2) {
                long total = (pow26[m] - (newDp0 + newDp1)) % MOD;
                if (total < 0) {
                    total += MOD;
                }
                sum = (sum + total) % MOD;
            }

            dp0 = newDp0;
            dp1 = newDp1;
        }

        System.out.println(sum);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 预先计算幂次：通过数组pow26存储26的各次幂模1e9+7的结果，避免重复计算。
2. 动态规划状态转移：dp0和dp1分别维护没有'u'和有'u'但没有's'的状态。每次迭代更新这两个状态。
3. 累加结果：对于每个长度大于等于2的情况，计算该长度下包含子序列"us"的字符串数量，并累加到总和中。
4. 处理负数情况：由于取模运算可能导致负数结果，通过加MOD确保结果非负。