サブ配列の合計が指定された場合の配列要素の検索

Question

N要素の配列には、1からNのインデックスが付けられます。すべての要素は不明で整数です。 A、B、Cの形式のクエリがある場合、Aは開始インデックス、Bは終了インデックス、CはAとBの間のすべての要素の合計です。配列のすべての要素を調べる。例：

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

これに対する1つの有効な解決策がある：

2, -3, 1, 6 

制約：

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

与えられた基準を満たす任意のソリューションが受け入れられ、十分なクエリを想定しているが、すべてを見つけるために与えられています要素。

Answer 1

これを解決する1つの方法は、問題を一連の連立方程式として扱うことです。それぞれの総和は、最大n個の変数の線形方程式を与えます。したがって、整数値を持つ方程式の解を見つけることができれば、すべて設定する必要があります。 K個の異なる制約を有するn個の変数の一連のガウス消去を使用

が期待にO（K ）時間（すなわち、N = O（k）を仮定して）かかり（システムを想定良条件です）。そこから、整数解を見つけることは容易でなければならない。任意の1つの解ベクトルの共通分母を見つけ、それによって乗算するだけです。

希望すると便利です。