关于本题正解复杂度的一点小问题

RT

没具体思考，问一下正解是 $O(n^4)$ 的还是 $O(n^3)$ 的啊。

如果是前者的话，我们知道自然数幂和可以 $O(n)$ 求，那么有没有可能通过奇怪的换根或者优化转移做到 $O(n^3)$ 或 $O(n^3\operatorname{polylog})$？