小红的链表节点染色

[题目链接](https://www.nowcoder.com/practice/43369411700648e8bc78932bcabf04d0)

思路

题目要求：给定一个链表，其中部分节点已被染成红色（'R'），选择一些未染色节点（'W'）染红，使得所有红色节点的权值之和为偶数。求方案数，对 $10^9 + 7$ 取模。

关键观察：奇偶性分析

一个数的和是否为偶数，只取决于其中奇数的个数的奇偶性。因此只需关注每个节点值的奇偶性。

将未染色节点分为两类：

偶数值节点（共 $e$ 个）：无论是否染红，都不改变总和的奇偶性，因此可以任意选择。
奇数值节点（共 $o$ 个）：每选一个奇数，总和的奇偶性翻转一次。

设已染红节点的权值之和的奇偶性为 $p$ （ $p = 0$ 表示偶数， $p = 1$ 表示奇数）。

分类讨论

偶数值节点：每个有选或不选两种选择，贡献 $2^e$ 种方案。

奇数值节点：需要从 $o$ 个奇数节点中选出一个子集，使得选出个数的奇偶性恰好抵消 $p$ ：

若 $p = 0$ ：需要选出偶数个奇数节点。
若 $p = 1$ ：需要选出奇数个奇数节点。

当 $o \geq 1$ 时， $o$ 个元素的子集中，恰好有 $2^{o-1}$ 个子集大小为偶数， $2^{o-1}$ 个子集大小为奇数。因此满足条件的方案数为 $2^{o-1}$ 。

当 $o = 0$ 时，没有奇数节点可选，总和奇偶性固定为 $p$ 。若 $p = 0$ 则方案数为 $2^e$ ，否则为 $0$ 。

最终公式

\text{ans} = \begin{cases}

2^e \times 2^{o-1} & o \geq 1 \\

2^e & o = 0 \text{ 且 } p = 0 \\

0 & o = 0 \text{ 且 } p = 1

\end{cases}

代码

C++
Java

class Solution {
public:
    int getMethod(ListNode* head, string colors) {
        const int MOD = 1e9 + 7;
        int redParity = 0;
        int oddW = 0, evenW = 0;

        ListNode* cur = head;
        for (int i = 0; cur; i++, cur = cur->next) {
            if (colors[i] == 'R') {
                redParity = (redParity + cur->val % 2) % 2;
            } else {
                if (cur->val % 2 == 1) oddW++;
                else evenW++;
            }
        }

        auto power = [&](long long base, long long exp) -> long long {
            long long res = 1;
            base %= MOD;
            while (exp > 0) {
                if (exp & 1) res = res * base % MOD;
                base = base * base % MOD;
                exp >>= 1;
            }
            return res;
        };

        long long evenFree = power(2, evenW);
        if (oddW == 0) {
            return redParity == 0 ? (int)(evenFree % MOD) : 0;
        }
        return (int)(evenFree % MOD * power(2, oddW - 1) % MOD);
    }
};

import java.util.*;

public class Solution {
    public int getMethod(ListNode head, String colors) {
        final int MOD = 1000000007;
        int redParity = 0;
        int oddW = 0, evenW = 0;

        ListNode cur = head;
        for (int i = 0; cur != null; i++, cur = cur.next) {
            if (colors.charAt(i) == 'R') {
                redParity = (redParity + cur.val % 2) % 2;
            } else {
                if (cur.val % 2 == 1) oddW++;
                else evenW++;
            }
        }

        long evenFree = power(2, evenW, MOD);
        if (oddW == 0) {
            return redParity == 0 ? (int)(evenFree % MOD) : 0;
        }
        return (int)(evenFree % MOD * power(2, oddW - 1, MOD) % MOD);
    }

    private long power(long base, long exp, int mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) res = res * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return res;
    }
}

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 为链表长度。遍历链表一次统计奇偶性，快速幂 $O(\log n)$ 。
空间复杂度： $O(1)$ 。只使用了常数个变量。