Atcoder ABC259H Yet Another Path Counting
首先可以想到有组合数的方法：
令起点为 \((x1, y1)\)，终点为 \((x2, y2)\)，则路径方案数就为 \(\binom{x2 + y2 - x1 - y1}{x2 - x1}\)，这样设有 \(k\) 个相同颜色的点，时间复杂度就为 \(O(k^2)\)。
再考虑到还有 \(\text{DP}\) 方法：
令 \(f_{x, y}\) 为走到 \((x, y)\) 的方案数，不限制起点。
对于颜色都为 \(c\) 的点 \((x, y)\) 每个都可能成为起点，令 \(f_{x, y} = 1\)，转移式就为 \(f_{x, y}\leftarrow f_{x, y} + f_{x - 1, y} + f_{x, y - 1}\)，最后再统计每个点为终点的方案数 \(\sum\limits_{col_{x, y} = c} f_{x, y}\)。
时间复杂度就为 \(O(n^2)\)。
发现第一种方法在点数少时更优秀，第二种方法在点数多时更优秀，考虑设定一个阙值 \(B\)，在点数 \(\le B\) 时用第一种，\(> B\) 时用第二种。
对于第一种方法，上界肯定要尽量都是 \(B\)，时间复杂度 \(O(\frac{n^2}{B}\times B^2)\)，即 \(O(n^2B)\)；对于第二种方法，最多会出现 \(\frac{n^2}{B}\) 次这种情况，所以时间复杂度为 \(O(\frac{n^4}{B})\)。
于是总时间复杂度为 \(O(n^2B + \frac{n^4}{B})\)，当 \(B = n\) 时最优，时间复杂度为 \(O(n^3)\)。