Today, while working on 1932E, I came up with a construction method that might be correct. However, this approach times out at the 13th test point. I believe finding a valid path is the bottleneck of my algorithm.

Now, I have simplified the approach to finding a valid path in 1932E and want to ask if there is a method with a time complexity of $$$O(n^3)$$$ or better.

Given an $$$n\times n$$$ matrix and an integer $$$k$$$, you need to start from $$$(1,1)$$$ and move to $$$(n,n)$$$, where you can only move one step down or one step to the right each time. The task is to find a valid path such that the sum of all numbers on the path equals $$$k$$$.

• $$$2\le n\le 25,1\le k\le 10^{13}$$$.

• Ensure that the data is generated randomly.

Here are the Chinese description.

给定一个 $$$n\times n$$$ 的矩阵和一个整数

Unable to parse markup [type=CF_MATHJAX]

是否有一种 $$$O(n^3)$$$ 或更好的做法。