To solve this problem, we need to count the number of subarrays where the product of elements is divisible by 100. Since 100 = 2² * 5², a product is divisible by 100 if it contains at least two 2s and two 5s in its prime factorization.

Approach

1. Prime Factorization: For each element, compute the count of 2s and 5s in its prime factorization.
2. Prefix Counts: Maintain prefix counts of 2s and 5s up to each position in the array. This helps in quickly calculating the number of 2s and 5s in any subarray.
3. Fenwick Tree with Sorted Lists: Use a Fenwick Tree (Binary Indexed Tree) where each node stores a sorted list of prefix counts of 2s. This allows efficient querying of the number of valid subarrays ending at the current position.

Key Observations

• Non-Decreasing Prefix Counts: The prefix counts of 2s and 5s are non-decreasing since each element contributes non-negative counts of these primes.
• Efficient Query: For each position, we need to find the number of previous positions where the difference in prefix counts of 2s and 5s is at least 2. This is done using the Fenwick Tree to query valid previous positions.

Solution Code

import bisect

def count_2_5(x):
    cnt2 = 0
    while x % 2 == 0:
        cnt2 += 1
        x = x // 2
    cnt5 = 0
    while x % 5 == 0:
        cnt5 +=1
        x = x //5
    return cnt2, cnt5

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))

    # Compute prefix counts of 2 and 5
    prefix2 = [0]*(N+1)
    prefix5 = [0]*(N+1)
    for i in range(1, N+1):
        cnt2, cnt5 = count_2_5(A[i-1])
        prefix2[i] = prefix2[i-1] + cnt2
        prefix5[i] = prefix5[i-1] + cnt5

    # Generate sorted unique p5 values (since prefix5 is non-decreasing)
    unique_p5 = []
    prev = -1
    for p in prefix5:
        if p != prev:
            unique_p5.append(p)
            prev = p
    rank_dict = {v:i+1 for i, v in enumerate(unique_p5)}  # 1-based rank
    size_tree = len(unique_p5)

    # Fenwick Tree: each node is a sorted list (appended in non-decreasing order)
    tree = [[] for _ in range(size_tree + 1)]

    def update(rank, val):
        while rank <= size_tree:
            tree[rank].append(val)
            rank += rank & -rank

    def query(rank, max_val):
        res =0
        while rank > 0:
            # number of elements <= max_val in tree[rank]
            res += bisect.bisect_right(tree[rank], max_val)
            rank -= rank & -rank
        return res

    ans = 0
    # Add the initial prefix (0,0)
    update(rank_dict[prefix5[0]], prefix2[0])

    for i in range(1, N+1):
        current_p2 = prefix2[i]
        current_p5 = prefix5[i]

        Y = current_p5 -2
        if Y < 0:
            # No valid previous prefix
            update(rank_dict[current_p5], current_p2)
            continue

        # Find the maximum rank where p5 <= Y
        # Since unique_p5 is sorted, use bisect_right
        idx = bisect.bisect_right(unique_p5, Y)
        if idx == 0:
            update(rank_dict[current_p5], current_p2)
            continue

        query_r = idx  # since unique_p5[0..idx-1] <= Y, rank is idx (1-based)
        max_val = current_p2 - 2
        if max_val < 0:
            update(rank_dict[current_p5], current_p2)
            continue

        cnt = query(query_r, max_val)
        ans += cnt

        # Add current prefix to the tree
        update(rank_dict[current_p5], current_p2)

    print(ans)

if __name__ == "__main__":
    main()

Explanation

1. Prime Factorization: For each element, we count the number of 2s and 5s in its prime factors.
2. Prefix Counts: We maintain cumulative counts of 2s and 5s up to each position.
3. Fenwick Tree: This data structure helps in efficiently querying the number of valid previous positions. Each node in the tree stores a sorted list of prefix counts of 2s, allowing quick binary search to find valid entries.
4. Query: For each position, we query the Fenwick Tree to find the number of previous positions where the difference in prefix counts of 2s and 5s is at least 2, which gives the number of valid subarrays ending at the current position.

This approach ensures that we handle large input sizes efficiently, with a time complexity of O(N log M log K), where M is the number of unique prefix counts of 5s and K is the average size of the lists in the Fenwick Tree nodes. This makes the solution scalable for large N up to 100,000.

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