求含至多K个唯一元素的无重复子序列计数的高效解法

Hey there! Let's break down how to solve this problem efficiently, since brute-forcing with itertools.combinations is totally infeasible for large N (like 1e6).

Problem Analysis #

First, let's restate the core of the problem: we need to count all subsequences where:

1. No duplicate values are present (each value can appear at most once in the subsequence)
2. The length of the subsequence is ≤ K

The key insight here is that each unique value contributes independently to the count: if a value appears c times, we have c+1 choices for it (either skip it entirely, or pick one of its c occurrences). But since we're limited to subsequences of length ≤ K, we can't just multiply all (1+c) terms directly (that would count all possible valid subsequences, including those longer than K).

Efficient Approach Using Dynamic Programming #

We'll use dynamic programming to track the number of valid subsequences for each possible length from 0 to min(K, m) (where m is the number of unique values in the input). Here's the step-by-step plan:

1. Count Occurrences: First, we count how many times each value appears in the input. Since A_i ≤ 9000, we can use a fixed-size array for this (way faster than a hash map for large N).
2. Dynamic Programming Setup: Let dp[t] represent the number of valid subsequences of length t. Initialize dp[0] = 1 (the empty subsequence) and all other dp[t] = 0.
3. Update DP Array: For each unique value with count c:
   • Iterate t from min(K, current_max_length) down to 1 (reverse iteration avoids overwriting values we still need to use).
   • Update dp[t] += dp[t-1] * c: this accounts for adding one of the c occurrences of the current value to all existing subsequences of length t-1.
4. Calculate Result: Sum all values in dp from index 0 to min(K, m)—this gives the total number of valid subsequences.

Optimization for Large K

If K ≥ m (we can choose all unique values without exceeding the length limit), we can skip the DP step entirely. The total number of valid subsequences is just the product of (1 + c) for all unique values (each term represents choosing to include or exclude the value, with c ways to include it).

Code Implementation #

Here's a Python implementation that handles all cases efficiently:

def count_valid_subsequences(arr, K):
    # Step 1: Count occurrences of each value (A_i <= 9000)
    max_value = 9000
    count_array = [0] * (max_value + 1)
    for num in arr:
        count_array[num] += 1
    
    # Collect counts of values that actually appear
    non_zero_counts = [c for c in count_array if c > 0]
    m = len(non_zero_counts)
    max_t = min(K, m)
    
    # Case 1: K is large enough to include all unique values
    if K >= m:
        result = 1
        for c in non_zero_counts:
            result *= (1 + c)
        return result
    
    # Case 2: Use DP to count subsequences up to length K
    dp = [0] * (max_t + 1)
    dp[0] = 1  # Empty subsequence
    
    for c in non_zero_counts:
        # Iterate backwards to avoid overwriting dp[t-1] before using it
        for t in range(max_t, 0, -1):
            dp[t] += dp[t-1] * c
    
    # Sum all valid subsequence lengths (0 to max_t)
    return sum(dp)

# Test with the example input
example_arr = [2, 3, 3, 7, 5]
example_K = 3
print(count_valid_subsequences(example_arr, example_K))  # Output: 22

Time Complexity #

• Counting Occurrences: O(N) — linear time to traverse the input array, which is acceptable even for N=1e6.
• DP Step: O(m * min(K, m)) — since m ≤ 9000, this is at most 9000*9000 = 81 million operations, which is manageable in Python within 1 second.
• Large K Optimization: O(m) — just a single pass over the unique counts, which is blazingly fast.

Why This Works #

Let's verify with the example input [2,3,3,7,5] and K=3:

• Non-zero counts are [1, 2, 1, 1] (for values 2,3,7,5)
• After processing all counts, dp becomes [1,5,9,7]
• Sum is 1+5+9+7=22, which matches the example result.

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