
ZOJ Problem Set  4003
We define \(\sum a_i  b_i^p\) as the distance of two vectors \((a_1, a_2, \dots, a_n)\) and \((b_1, b_2, \dots, b_n)\) where \(p\) is a given integer. Only two vectors with the same number of integers have distance between them. Now please find the number of subvector pairs from vector \(X = (x_1, x_2, ..., x_n)\) and \(Y = (y_1, y_2, ..., y_n)\) respectively, such that the distance between the two subvectors is no more than \(V\). A subvector means a successive part of the referencing vector. InputThe first line contains an integer \(T\) (\(1 \le T \le 10^4\)), representing the number of test cases. There are only about 10 big cases. For each test case: The first line contains three integers \(n\), \(V\), and \(p\) (\(1 \le n \le 10^3\), \(0 \le V \le 10^{18}\), \(p \in \{1, 2, 3\}\)). The following line contains \(n\) nonnegative integers \(x_1, x_2, \dots, x_n\) (\(0 \le x_i^p \le 10^9\)), indicating the vector \(X\). The following line contains \(n\) nonnegative integers \(y_1, y_2, \dots, y_n\) (\(0 \le y_i^p \le 10^9\)), indicating the vector \(Y\). OutputFor each test case output one single line, representing the number of required vector pairs. Sample Input2 5 2 1 1 1 1 1 1 1 1 1 1 1 5 0 2 2 1 3 4 5 5 4 3 2 1 Sample Output55 6 HintIn sample 1, for subvector with length 1, any subvector in \(X\) is equal to that in \(Y\), so there are 25 pairs. For subvector with length 2, 3, 4, 5 the number of pairs are 16, 9, 4, 1 respectively. So the answer is 55. In Sample 2, the six pairs are: (1)(1), (2)(2), (3)(3), (4)(4), (5)(5) and (2, 1)(2, 1). Author: ZHANG, Yuan Source: ZOJ Monthly, January 2018 