To solve this problem, we need to determine the number of non-empty subsets of a given sequence of numbers such that the sum of the subset is divisible by 3. The solution involves analyzing the remainders of the numbers when divided by 3 and using dynamic programming to count valid subsets.

Approach

1. Count Remainders: First, count the number of elements with remainders 0, 1, and 2 when divided by 3. Let these counts be cnt0, cnt1, and cnt2 respectively.
2. Dynamic Programming for Subsets: For elements with remainder 1 and 2, compute the number of subsets that result in each possible remainder (0, 1, 2) when their counts are considered modulo 3.
3. Combine Results: Calculate valid combinations of subsets from elements with remainder 1 and 2 such that their sum modulo 3 is zero. Multiply this by the number of valid subsets from elements with remainder 0 (since any subset of these elements does not affect the sum modulo 3).
4. Adjust for Non-Empty Subsets: Subtract 1 from the total to exclude the empty subset.

Solution Code

MOD = 10**9 + 7

def compute_f(n):
    f0, f1, f2 = 1, 0, 0
    for _ in range(n):
        new0 = (f0 + f2) % MOD
        new1 = (f1 + f0) % MOD
        new2 = (f2 + f1) % MOD
        f0, f1, f2 = new0, new1, new2
    return (f0, f1, f2)

def pow_mod(a, b):
    res = 1
    while b > 0:
        if b % 2 == 1:
            res = (res * a) % MOD
        a = (a * a) % MOD
        b = b // 2
    return res

def main():
    import sys
    input = sys.stdin.read().split()
    arr = list(map(int, input))
    cnt0 = cnt1 = cnt2 = 0
    for num in arr:
        rem = num % 3
        if rem == 0:
            cnt0 += 1
        elif rem == 1:
            cnt1 += 1
        else:
            cnt2 += 1

    f1_0, f1_1, f1_2 = compute_f(cnt1)
    f2_0, f2_1, f2_2 = compute_f(cnt2)

    g1_0 = f1_0
    g1_1 = f1_1
    g1_2 = f1_2

    g2_0 = f2_0
    g2_1 = f2_2  # sum mod3=1 when count mod3=2
    g2_2 = f2_1  # sum mod3=2 when count mod3=1

    C = (g1_0 * g2_0 + g1_1 * g2_2 + g1_2 * g2_1) % MOD
    pow2 = pow_mod(2, cnt0)
    total = (C * pow2) % MOD
    ans = (total - 1 + MOD) % MOD  # subtract empty subset

    print(ans)

if __name__ == "__main__":
    main()

Explanation

1. Count Remainders: We count how many elements have remainders 0, 1, and 2 when divided by 3. This helps in breaking down the problem into manageable parts.
2. Dynamic Programming: The compute_f function calculates the number of subsets of n elements that result in each remainder (0,1,2) when their count is modulo 3. This is done using a recurrence relation where each element can either be included or excluded.
3. Combine Valid Subsets: For elements with remainder 1 and 2, we find valid combinations of subsets such that their sum modulo 3 is zero. This includes combinations like 0 from both, 1 from remainder 1 and 1 from remainder 2, etc.
4. Adjust for Non-Empty: The empty subset is excluded by subtracting 1 from the total count of valid subsets.

This approach efficiently handles the problem constraints and provides the correct result modulo (10^9 +7). The use of dynamic programming ensures that we count all valid subsets without explicitly generating them, making the solution scalable.

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