To solve this problem, we need to count the number of valid strings of length ( n ) composed of characters A, B, and C, adhering to two constraints: no two A's are consecutive, and the number of B's is even.

Approach

We use dynamic programming (DP) to efficiently compute the result. The key insight is to track four states that capture the necessary information about the current string:

1. s00: Number of valid strings ending with a non-A character and having an even count of B's.
2. s01: Number of valid strings ending with a non-A character and having an odd count of B's.
3. s10: Number of valid strings ending with A and having an even count of B's.
4. s11: Number of valid strings ending with A and having an odd count of B's.

Transitions:

• s00: Can be formed by adding C to any string with even B's or adding B to any string with odd B's (since adding B flips the count).
• s01: Can be formed by adding C to any string with odd B's or adding B to any string with even B's.
• s10: Can only be formed by adding A to a string ending with non-A and having even B's (since no consecutive A's).
• s11: Can only be formed by adding A to a string ending with non-A and having odd B's.

Solution Code

MOD = 10**9 + 7

n = int(input())
if n == 0:
    print(1)
else:
    s00, s01, s10, s11 = 1, 0, 0, 0  # Base case: empty string
    for _ in range(n):
        new_s00 = (s00 + s10 + s01 + s11) % MOD
        new_s01 = new_s00  # Same as new_s00 due to commutative sum
        new_s10 = s00 % MOD
        new_s11 = s01 % MOD
        s00, s01, s10, s11 = new_s00, new_s01, new_s10, new_s11
    print((s00 + s10) % MOD)

Explanation

• Base Case: The empty string (length 0) has 1 valid way (no characters), so s00 = 1 (even B count, non-A ending).
• Iteration: For each length from 1 to ( n ), we update the states using the transitions mentioned.
• Result: The valid strings with even B counts are the sum of s00 (non-A ending, even B) and s10 (A ending, even B).

This approach runs in ( O(n) ) time and uses ( O(1) ) space, making it efficient even for large values of ( n ). The result is taken modulo ( 10^9 +7 ) to handle large numbers.

Example:

• For ( n=1 ), the valid strings are A and C → result is 2.
• For ( n=2 ), the valid strings are AC, BA, BB, BC, CA, CC → result is 4 (corrected to 4 as per constraints).

This solution correctly handles all cases and provides the desired result efficiently.

作者声明:本文包含人工智能生成内容。