固定首尾的非连续重复字符序列排列数求解及DP方案疑问

Hey there! Let's break down this problem properly and refine your dynamic programming approach, plus share some smarter optimizations for larger inputs.

First, let's clarify the exact problem we're solving:
We have M distinct characters, need to build a sequence of length N where:

1. No two adjacent characters are the same
2. The first character is fixed (let's say it's character 0 for simplicity) and the last character is fixed to a different one (say character 1)

1. Fixing Your Original DP Approach #

Your core DP idea is solid, but there are a couple of tweaks needed to make it correct:

State Definition #

You defined dp[i][j] as the number of valid sequences of length i that end with the j-th character (we'll index characters 0 to M-1). That's perfect.

Initialization #

Your initial setup had dp[1][0] = 1 and dp[1][1] = 1—that's wrong. Since the first character is fixed to 0, a sequence of length 1 can only end with 0. So:

vector<vector<long long>> dp(N+1, vector<long long>(M, 0));
dp[1][0] = 1; // Only valid sequence is [0]

(Use long long instead of int to avoid overflow for larger N/M!)

State Transition #

Your triple loop works, but it's inefficient. Instead of summing all k != j each time, we can precompute the total number of valid sequences of length i-1, then subtract the count of sequences that end with j (since we can't have adjacent duplicates):

for (int i = 2; i <= N; i++) {
    // Calculate total valid sequences of length i-1
    long long total = 0;
    for (int k = 0; k < M; k++) {
        total += dp[i-1][k];
    }
    // For each character j, sequences ending with j = total - sequences ending with j (prev step)
    for (int j = 0; j < M; j++) {
        dp[i][j] = total - dp[i-1][j];
    }
}

This cuts the time complexity from O(N*M²) to O(N*M)—way better for larger M.

Final Result #

Since we need sequences that end with character 1, the answer is simply dp[N][1]—no need to sum other values like you mentioned earlier.

2. Even Faster: Mathematical Formula (O(1) Time) #

For very large N (like 1e9), even the optimized DP is too slow. We can derive a closed-form formula using recurrence relations:

Let's define:

• a[n]: Number of valid sequences of length n starting with 0 and ending with 0
• b[n]: Number of valid sequences of length n starting with 0 and ending with any character not 0

We know:

• Total valid sequences of length n starting with 0: a[n] + b[n] = (M-1)^(n-1) (each step after the first has M-1 choices)
• a[n] = b[n-1] (to end with 0, the previous character must not be 0)
• b[n] = (M-1)^(n-1) - a[n] = (M-1)^(n-1) - b[n-1]

Solving this recurrence gives us:
b[n] = [(M-1)^n + (-1)^n * (M-1)] / M

Since we want sequences ending with a specific non-0 character (like 1), we divide b[n] by (M-1) (all non-0 endings are symmetric):

Final Count = [(M-1)^(N-1) + (-1)^N] / M

Example Checks #

• M=2, N=3: [(1)^2 + (-1)^3]/2 = (1-1)/2 = 0 (correct—no valid sequences: 0→1→1 is invalid, 0→0→1 is invalid)
• M=3, N=4: [(2)^3 + (-1)^4]/3 = (8+1)/3 = 3 (matches our manual count of valid sequences)

You can compute (M-1)^(N-1) efficiently using fast exponentiation to handle huge exponents.

3. Quick Recap of Best Approaches #

内容的提问来源于stack exchange，提问作者MocTriPsy