[Python 3/numpy] Think in the easiest way and let numpy do the else
Intuition\n Describe your first thoughts on how to solve this problem. \nI am familiar with numpy and it is surprisingly easy and tidy for this problem. In some
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI am familiar with numpy and it is surprisingly easy and tidy for this problem. In some cases, it\'s easy to consider if we split the path to several parts and count separately, then use the FFT-based convolution to combine them together.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSimilar to other solutions, we also split the houses to 3 parts: 1 circle and 2 chains connected to the circle. We call the number of houses on the circle as `c` and on the chains as `l` and `r`. Then, we count the pairs inside each part and between the parts. We can first count `(x,y)` and `(y,x)` as 1 pair and double the answer finally. We can also count the pairs `(x,x)` which distance are `0` and make our formula even simpler. Specifically, we have 4 cases:\n\n- `ll` and `rr`: Pairs inside the chains. For example, if `l=4`, the answer is `[4,3,2,1,0,...]`. Obviously, `ll = np.arange(l+1)[::-1]`\n- `all2c`: At least one end is in the circle. We split the distance to 2 steps: \n    1. get to the circle\n    If the other point is on the chains, the count of the possible steps are `l2c=[0] + [1] * l` and `r2c=[0] + [1] * r`; otherwise, the other point is already on the circle, so count are just `c2c=[c]`\n    2. walk in the circle\n    We walk in both directions and use the minimum one: `np.minimum(np.arange(c + 1), np.arange(c + 1)[::-1])`. Then, use `np.bincount` to count the numbers as `in_c`\n\n  Finally, we convolve the count of the 2 steps: `all2c = conv(l2c + r2c + c2c/2, in_c)`. We use `c2c / 2` to count the pairs inside the circle only once.\n\n- `lr`: From one chain to the other. We must first walk to the circle and the walk out. If the circle degenerate to a single point, we can simply walk in and out, so `lr = conv(l2c, r2c)`; otherwise, we need to spend `1` step inside the circle and we move the content of `lr` one step right: `lr[1:] = lr[:-1]`.\n\nFinally, we have `ans = ll + rr + all2c + lr`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*log\\ n)$$ (FFT-based convolution)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        import numpy as np\n        def tolist(arr):\n            return (arr.real + 0.5).astype(np.int64).tolist()\n        \n        def conv(arr1, arr2):\n            return np.fft.ifft(np.fft.fft(arr1) * np.fft.fft(arr2))\n        \n        zero = np.zeros(n + 1)\n        x, y = sorted([x, y])\n        l = x - 1\n        r = n - y\n        c = y - x + 1\n               \n        ll = zero.copy()\n        ll[:l+1] = np.arange(l+1)[::-1]\n        rr = zero.copy()\n        rr[:r+1] = np.arange(r+1)[::-1]\n        \n        dis_c = np.minimum(np.arange(c + 1), np.arange(c + 1)[::-1])[:-1]\n        in_c = np.bincount(dis_c, minlength=n+1)\n\n        l2c = zero.copy()\n        l2c[1:l + 1] = 1\n        r2c = zero.copy()\n        r2c[1:r + 1] = 1\n        c2c = zero.copy()\n        c2c[0] = c\n        all2c = conv(l2c + r2c + c2c / 2, in_c)\n\n        lr = conv(l2c, r2c)\n        if x != y:\n            lr[1:] = lr[:-1]\n        \n        ans = ll + rr + all2c + lr\n        return tolist(ans[1:] * 2)\n```
['Math', 'Counting', 'Python3']