Inclusion–exclusion principle O(n) solution
Intuition\nUse inclusion\u2013exclusion principle to handle pairs of nodes with simple formula.\n\n# Approach\nThere are two types of basic components: line & c
# Intuition\nUse inclusion\u2013exclusion principle to handle pairs of nodes with simple formula.\n\n# Approach\nThere are two types of basic components: line & cycle:\n1. line: for a line with `m` nodes the distances are given by `2 * (m - 1), 2 * (m - 2), ..., 2`.\n2. cycle: for a cycle with `c` nodes, there are two cases: odd & even. Say `div, odd = divmod(c, 2)`. If odd, the distances are given by `2 * c, 2 * c, ..., 2 * c` (`div` terms). If even, the distances are given by `2 * c, 2  * c, ..., 2 * c, c` (also `div` terms but there are only `c` pairs across).\n\nWith those inclusion\u2013exclusion principle gives the solution:\n1. If `abs(x - y) < 2`, the solution is given by a line with `n` nodes.\n2. Otherwise, sort (x, y) and start with the shortcut line with `n - (y - x - 1)` nodes & the cycle with `y - x + 1` nodes.\n3. We double-counted (x, y), so substract it out.\n4. Then we count stem-nodes-to-cycle-nodes distances. We do it twice: one for nodes before `x`, the other for nodes after `y`. For each stem-cycle there are two branches with lengths `x + div` and `x + div (- 1)`(depending on whether it\'s even or odd.\n5. The parts of the branches covered by the shortcut line & cycle are double-counted, so we subtract them out.\n6. This time (x, y) as part of both the shortcut line & cycle are subtracted twice, so we add them back.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```python\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        ans = [0] * n\n        \n        def count(m, sign=1):\n            for i in range(1, m):\n                ans[i - 1] += sign * 2 * (m - i)\n        \n        if abs(x - y) < 2:\n            count(n)\n            return ans\n        \n        if x > y:\n            x, y = y, x\n        # Cycle:\n        c = y - x + 1\n        div, odd = divmod(c, 2)\n        if odd:\n            for i in range(1, div + 1):\n                ans[i - 1] += 2 * c\n        else:\n            for i in range(1, div):\n                ans[i - 1] += 2 * c\n            ans[div - 1] += c\n             \n        # Shortcut:\n        m = n - (y - x - 1)\n        count(m)\n        \n        # (x, y) double-count:\n        ans[0] -= 2\n\n        def stem_cycle(x):\n            if odd:\n                count(x + div, 2)\n                count(x, -1)\n                count(x + 1, -1)\n                count(div + 1, -2)\n            else:\n                count(x + div - 1)\n                count(x + div)\n                count(x, -1)\n                count(x + 1, -1)\n                count(div + 1, -1)\n                count(div, -1)\n            # (x, y) double-count:\n            ans[0] += 2\n\n        stem_cycle(x)\n        stem_cycle(n - y + 1)\n        return ans\n```
['Python3']