33. 卡牌翻面求和问题问题描述

小M有 nnn 张卡牌，每张卡牌的正反面分别写着不同的数字，正面是 aia_iai​，背面是 bib_ibi​。小M希望通过选择每张卡牌的一面，使得所有向上的数字之和可以被 3 整除。我们需要告诉小M，一共有多少种不同的方案可以满足这个条件。由于可能的方案数量过大，结果需要对 109+710^9 + 7109+7 取模。

思路解析1. 问题本质

每张卡牌可以选择正面或背面，其中每个选择会影响卡牌所代表的数字。目标是找到所有选择方案，使得最终所有卡牌的数字之和能够被 3 整除。由于卡牌的数字正反面是给定的，我们可以看作每张卡牌为两种可能的贡献值 aia_iai​（正面）或 bib_ibi​（背面），并且希望最终选择的数字和对 3 取余后为 0。

2. 状态定义

我们可以通过动态规划来解决这个问题。设定一个状态 dp[i][j]，表示前 iii 张卡牌中，所有已选数字之和对 3 取余后为 jjj 的方案数。jjj 可以取值 0、1、2，表示和对 3 的余数分别是 0、1、2。

3. 状态转移

对于第 iii 张卡牌，有两种选择：

状态转移公式为：

dp[i][j]=(dp[i−1][(j−ai%3+3)%3]+dp[i−1][(j−bi%3+3)%3])mod(109+7)dp[i][j]=(dp[i−1][(j−a_i \% 3+3) \% 3]+dp[i−1][(j−b_i\%3+3)\%3])mod(10^9+7)dp[i][j]=(dp[i−1][(j−ai​%3+3)%3]+dp[i−1][(j−bi​%3+3)%3])mod(109+7)

4. 最终答案

我们需要的是所有卡牌选择后的结果，使得数字和对 3 取余的值为 0，即 dp[n][0]，即最后一张卡牌后，和为 0 的方案数。

代码实现

def solution(n: int, a: list, b: list) -> int:
    MOD = 10**9 + 7
    # dp[i][j] 表示前 i 张卡牌选择后和对 3 取余为 j 的方案数
    dp = [[0] * 3 for _ in range(n + 1)]
    dp[0][0] = 1  # 初始状态，没有卡牌时和为0的方案数为1
    
    # 遍历每张卡牌

    for i in range(1, n + 1):
        for j in range(3):
            # 对每一张卡牌，选择正面或者背面
            dp[i][j] = (dp[i-1][(j - a[i-1] % 3 + 3) % 3] + dp[i-1][(j - b[i-1] % 3 + 3) % 3]) % MOD
    
    # 返回最后一张卡牌选择后的和为0的方案数
    return dp[n][0]
# 测试用例
if __name__ == '__main__':
    print(solution(n = 3, a = [1, 2, 3], b = [2, 3, 2]) == 3)
    print(solution(n = 4, a = [3, 1, 2, 4], b = [1, 2, 3, 1]) == 6)
    print(solution(n = 5, a = [1, 2, 3, 4, 5], b = [1, 2, 3, 4, 5]) == 32)

解题思路详解

初始化：

状态转移：

最终结果：

复杂度分析