To solve this problem, we need to count the number of valid pairs (i, j) such that (i \leq j) and (A[i] + A[j] = B[i] + B[j]) for given sequences (A) and (B).

Approach

The key insight here is to transform the problem into a simpler form using a helper array. Let's define (C[k] = A[k] - B[k]). The equation (A[i] + A[j] = B[i] + B[j]) can be rewritten as (C[i] + C[j] = 0) (since (A[i] - B[i] + A[j] - B[j] = 0)).

We need to count two types of valid pairs:

1. Case 1: Pairs where (i = j) and (C[i] = 0) (since (C[i] + C[i] = 0) implies (C[i] = 0)).
2. Case 2: Pairs where (i < j) and (C[i] = -C[j]) (since (C[i] + C[j] = 0)).

Efficient Calculation:

• Case 1: Count the number of zeros in array (C).
• Case 2: Use a frequency map to track the occurrences of elements in (C) as we iterate through the array. For each element (C[j]), the number of valid pairs (i, j) with (i < j) is the number of times (-C[j]) has appeared before (j).

Solution Code

import sys
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

    count_zero = 0
    freq = defaultdict(int)
    case2 = 0

    for a, b in zip(A, B):
        c = a - b
        if c == 0:
            count_zero += 1
        # Add the number of valid i < j pairs for current c
        case2 += freq.get(-c, 0)
        # Update frequency map with current c
        freq[c] += 1

    total = case2 + count_zero
    print(total)

if __name__ == "__main__":
    main()

Explanation

1. Transformation: Convert sequences (A) and (B) into array (C) where each element is the difference between corresponding elements of (A) and (B).
2. Count Zeros: Track the number of zeros in (C) (Case 1).
3. Frequency Map: For each element in (C), check how many times its negative value has been seen before (Case 2). This gives valid pairs (i, j) where (i < j).
4. Total: Sum the counts from both cases to get the final result.

This approach runs in (O(n)) time complexity (using a frequency map with average (O(1)) operations per element) and uses (O(n)) space (for storing the frequency map). This makes it efficient for large input sizes.

Example Walkthrough

Let’s take an example to see how the solution works:

• (A = [0, 1, 0, 0]) and (B = [0, 0, 1, 0]) → (C = [0,1,-1,0]).
• Case1: Number of zeros in (C) → (2) (indices (0) and (3)).
• Case2: Valid pairs (i < j) → (0, 3) (since (C[0] = -C[3] =0) but wait, no—wait (C[0] + C[3] =0+0=0) → yes, and (1, 2) (1 + (-1)=0). So Case 2 count is (2).
• Total: (2+2=4), which is correct.

This confirms the solution works for the given example.

The final answer is the sum of Case1 and Case2 counts, which is the number of valid pairs (i,j) as required. (\boxed{4}) (for the example above, but the code will output the correct value for any input).

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