特殊数组方程的校验子集和

Question

我正在尝试解决以下问题。

我们得到N和A

N <= 5000
A[0] <= 10^6 and even 
if i is odd then 
A[i] >= 3 * A[i-1]
if i is even
A[i]= 2 * A[i-1] + 3 * A[i-2]
element at odd index must be odd and at even it must be even.

我们需要最小化数组的和。

我们得到了Q个数字

 Q <= 1000
 X<= 10^18

我们需要确定是否可以从我们的数组中获得subset-sum =X。

我试过的是，

创建最小和数组很容易。只要遵循方程式和约束即可。

据我所知，子集求和的方法是动态编程，它的时间复杂度是sum*sizeof(Array)，但是由于sum可以达到10^18，所以这种方法不起作用。

有没有我遗漏的方程式关系？

Answer 1

我们可以用一些数学方法来实现:对不起，latex，我不确定它在堆栈上是不是可能的？

让X_n作为序列(与您的A定义的序列相同)

我假设X_0是阳性的。

因此，序列是严格递增的，并且当X_{2n+1} = 3X_{2n}时会出现最小化

我们可以计算X_{2n}和X_{2n+1}的通项

v_0 = 
X0
X1

v_1 = 
X1
X2

v_0和v_1之间的关系是

M_a = 
0 1
3 2

v_1和v_2之间的关系是

M_b = 
0 1
0 3

因此，v_2和v_0之间的关系是

M = M_bM_a = 
3 2
9 6

我们推论

v_{2n} = 
X_{2n}
X_{2n+1}

v_{2n} = M^n v_0

遵循经典的对角化。我们(除非弄错了)得到

X_{2n} = 9^n/3 X_0 + 2*9^{n-1}X_1
X_{2n+1} = 9^n X_0 + 2*9^{n-1}/3X_1

回想一下，X_1 = 3X_0因此

X_{2n} = 9^n X_0
X_{2n+1} = 3.9^n X_0

现在，如果我们表示要以9为基数检查的总和，则会得到

       9^{n+1}        9^n
___   ________  ___   ___
      X^{2n+2}        X^2n

在X^{2n}位置中，我们只能放置1或0(这意味着我们从A中获取2n-th元素)，我们还可以在X^{2n}位置中放置3，这意味着我们从数组中选择了2n+1th元素

因此，我们只需在基本9中分解number，并检查它的所有数字是否都是0,1或3 (以及它的前导数字是否没有超出数组的界限……)