c++ - 在无法存储值的情况下计算系列？

Question

问题陈述[ here ]

Let be S a infinite secuence of integers:

S0 = a; S1 = b;

Si = |Si-2 - Si-1| for all i >= 2.

You have two integers a and b. You must answer some queries about the n-th element in the sequence.(means print the nth number in the sequence i.e S(n) )

( 0 <= a,b <= 10^18),( 1 <= q <= 100000 )

我尝试过的(这会导致运行时错误):

#include <bits/stdc++.h>
using namespace std;

long long int q,a,b,arr[100002];/*Can't declare an array of required size */
 
int main() {
    // your code goes here
    scanf("%lld%lld",&a,&b);
    arr[0]=a,arr[1]=b;
    scanf("%d",&q);
    int p[100002];
    long long int m = -1;//stores max index asked
    for(int i=0;i<q;i++)
    {
        scanf("%lld",&p[i]);
        m = (m>p[i])?m:p[i];
    }
    for(int i=2;i<=m;i++)//calculates series upto that index
    {
        arr[i]=abs(arr[i-1]-arr[i-2]);
    }
    for(int i=0;i<q;i++)
    {
        printf("%lld\n",arr[p[i]]);
    }
    return 0;
} 

Given : qi fits in 64 bit integer. since index can be very large and i cant declare that bit an array, how should i approach this problem(since brute force would give TLE). Thanks!

Answer 1

哈! 有一个不需要(完整)迭代的解决方案:

考虑一些值 Si和 Sj ，其中 i, j > 1 .然后，查看序列的数字是如何构建的(使用绝对值)，我们可以得出结论，两个数字都是正数。

那么它们的差值的绝对值保证小于(或等于)两者中较大的一个。

假设它严格小于两者中较大的值，在接下来的两个步骤中，原始值中较大的值将“超出范围”。由此我们可以得出结论，在这种情况下，序列的数量越来越少。

(*) 如果差值等于较大的一个，则另一个数字一定是 0 .在下一步中，可能会发生以下两种情况之一:

a) 较大的超出范围，那么接下来的两个数字是计算出的差值(等于较大的)和 0，这将再次产生较大的值。然后我们的情况与......

b) 零超出范围。然后下一步将计算较大的和计算出的差异(等于较大的)之间的差异，从而得到0 .在下一步中，这将回到原来的 (*) 情况。

结果: L 的重复模式, L , 0 , ...

一些例子:

3, 1, 2, 1, 1, 0, 1, 1, 0, ...
1, 3, 2, 1, 1, 0, 1, 1, 0, ...
3.5, 1, 2.5, 1.5, 1, .5, .5, 0, .5, .5, 0, ...
.1, 1, .9, .1, .8, .7, .1, .6, .5, .1, .4, .3, .1, .2, .1, .1, 0, ...

将其应用于代码:只要一个值是 0 ，不再需要迭代，接下来的两个数字将与前一个相同，然后再次出现0等等:

// A and B could also be negative, that wouldn't change the algorithm,
// but this way the implementation is easier
uint64_t sequence(uint64_t A, uint64_t B, size_t n) {
 if (n == 0) {
  return A;
 }
 uint64_t prev[2] = {A, B};
 for (size_t it = 1u; it < n; ++it) {
  uint64_t next =
    (prev[0] > prev[1]) ?
      (prev[0] - prev[1]) :
      (prev[1] - prev[0]);
  if (next == 0) {
   size_t remaining = n - it - 1;
   if (remaining % 3 == 0) {
    return 0;
   }
   return prev[0]; // same as prev[1]
  }
  prev[0] = prev[1];
  prev[1] = next;
 }
 return prev[1];
}

Live demo here (如果您愿意，可以使用 a 和 b 值)。

如果您对相同的 A 和 B 进行了重复查询，您可以缓存所有值直到 next == 0在 std::vector ，为您提供真正恒定的以下查询时间。

我也很确定在序列到达 0 之前存在一个模式，但我找不到它。

我只是注意到我错过了它应该是差异的绝对值......

如果它足够快，这是一个迭代版本:

// deciding on a concrete type is hard ...
uint64_t sequence (uint64_t A, uint64_t B, uint64_t n) {
 if (n == 0) {
  return A;
 }
 uint64_t prev[2] = {A, B};
 for (auto it = 1u; it < n; ++it) {
  auto next =
    (prev[0] > prev[1]) ?
      (prev[0] - prev[1]) :
      (prev[1] - prev[0]);
  prev[0] = prev[1];
  prev[1] = next;
 }
 return prev[1];
}

如您所见，您不需要存储所有值，只需要最后两个数字来计算下一个。

如果这还不够快，您可以添加内存:存储 prev 对有序中的值 std::map (将 n 映射到这些对)。然后，您可以从下一个较低的值 n 的条目开始。而不是从一开始。当然，您还需要管理该 map :保持它很小并充满“有用”的值。

这不是编程问题，而是算法问题。让我们看看该序列的第一个数字:

a
b
a-b
b-(a-b) = 2b-a
(a-b)-(b-(a-b)) = 2(a-b)-b = 2a-3b
2b-a-(2a-3b) = 5b-3a
2a-3b-(5b-3a) = 5a-8b
...

只看系数的绝对值表明......

b: 0 1 1 2 3 5 8 ...
a: (1) 0 1 1 2 3 5 ...

...这是关于斐波那契数列的。然后，还有标志，但这很容易:

b: - + - + - ...
a: + - + - + ...

所以你序列中的第 n 个数字应该等于

f(0) = a
f(n) = (-1)^n      * fib(n-1) * a +
       (-1)^(n-1)  * fib(n)   * b

当然现在我们必须计算第 n 个斐波那契数，但幸运的是已经有一个解决方案:

fib(n) = (phi^n - chi^n) / (phi - chi)
   with
  phi = (1 + sqr(5)) / 2
  chi = 1 - phi

所以，把它带到代码中:

unsigned long fib(unsigned n) {
 double const phi = (1 + sqrt(5)) / 2.0;
 double const chi = 1 - phi;
 return (pow(phi, n) - pow(chi, n)) / (phi - chi);
}
long sequence (long A, long B, unsigned n) {
 if(n ==0) {
  return A;
 }
 auto part_a = fib(n-1) * A;
 auto part_b = fib (n) * B;
 return (n % 2 == 0) ? (part_a - part_b) : (part_b - part_a);
}

一些 live demo is here ，但这在接近更大的数字时会出现问题(我怀疑 fib 变得不正确)。

该演示还包含序列的迭代版本，作为控制。如果这对您来说足够快，请改用它。无需存储比最后两个数字更多的任何内容。

为了进一步改进这一点，您可以使用带有孔的查找表来查找斐波那契数列，即记住序列的每十分之一(及其后继)数。