问题陈述[ 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!

最佳答案

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

考虑一些值 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, ...

// 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];
}

// 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];
}

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: + - + - + ...

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

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);
}

关于c++ - 在无法存储值的情况下计算系列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31663855/