arrays - 给定子数组之和时查找数组元素

Question

An array of N elements is given indexed from 1 to N. All elements are unknown and integers. Given some queries in the form of A, B, C where A is the starting index, B is the ending index and C is the sum of all elements between A and B inclusive. Find out all the elements of array. Example:

N=4
1, 3, 0
2, 4, 4

One valid solution to this is:

2, -3, 1, 6

Constraints:

1<=A<=B<=N, 2<=N<=65000, C<=1000000000

Any solution fulfilling the given criteria is accepted and assume enough queries are given to find out all the elements.

Answer 1

解决此问题的一种方法是将问题视为一系列联立方程。每个求和都会为您提供最多包含 n 个变量的线性方程，因此如果您能找到具有整数值的该方程的解，您应该已经准备就绪。

对具有 k 个不同约束的一系列 n 个变量使用高斯消去法需要(假设 n = O(k))O(k³) 期望时间(假设系统条件良好).从那里，找到整数解决方案应该很容易；只需找出任何一个解向量的公分母并乘以它即可。

希望这对您有所帮助!