{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWe 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.\u003c/p\u003e\n\n\u003cp\u003eNow please find the number of sub-vector pairs from vector \\(X \u003d (x_1, x_2, ..., x_n)\\) and \\(Y \u003d (y_1, y_2, ..., y_n)\\) respectively, such that the distance between the two sub-vectors is no more than \\(V\\). A sub-vector means a successive part of the referencing vector.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003eThe first line contains an integer \\(T\\) (\\(1 \\le T \\le 10^4\\)), representing the number of test cases. \u003cb\u003eThere are only about 10 big cases.\u003c/b\u003e For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe 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\\}\\)).\u003c/p\u003e\n\n\u003cp\u003eThe following line contains \\(n\\) non-negative integers \\(x_1, x_2, \\dots, x_n\\) (\\(0 \\le x_i^p \\le 10^9\\)), indicating the vector \\(X\\).\u003c/p\u003e\n\n\u003cp\u003eThe following line contains \\(n\\) non-negative integers \\(y_1, y_2, \\dots, y_n\\) (\\(0 \\le y_i^p \\le 10^9\\)), indicating the vector \\(Y\\).\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003eFor each test case output one single line, representing the number of required vector pairs.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n5 2 1\n1 1 1 1 1\n1 1 1 1 1\n5 0 2\n2 1 3 4 5\n5 4 3 2 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e55\n6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eIn sample 1, for sub-vector with length 1, any sub-vector in \\(X\\) is equal to that in \\(Y\\), so there are 25 pairs. For sub-vector with length 2, 3, 4, 5 the number of pairs are 16, 9, 4, 1 respectively. So the answer is 55.\u003c/p\u003e\n\n\u003cp\u003eIn Sample 2, the six pairs are: (1)(1), (2)(2), (3)(3), (4)(4), (5)(5) and (2, 1)(2, 1).\u003c/p\u003e\n"}}]}