计算系列无法存储值？ [英] Compute series without being able to store values?
问题描述
问题陈述[这里]
让s是整数的无限关系：
S0 = a;
S1 = b;
Si = | Si-2-Si-1 |对于所有的i> = 2。
你有两个整数a和b。您必须回答关于序列中第n个元素的一些查询（意味着打印序列中的第n个数字，即S（n））
<= a，b <= 10 ^ 18），（1≤q≤100000）
我试过的（这将给运行时错误）：
#include< bits / stdc ++。
using namespace std;
long long int q，a，b，arr [100002]; / *无法声明所需大小的数组* /
int main（）{
//你的代码在这里
scanf（％lld％lld，& a，& b）;
arr [0] = a，arr [1] = b;
scanf（％d，& q）;
int p [100002];
long long int m = -1; //存储最大索引请求
for（int i = 0; i
scanf（％lld ，& p [i]）;
m =（m> p [i]）？m：p [i];
}
for（int i = 2; i <= m; i ++）//计算直到该索引的序列
{
arr [i] = abs（arr [ 1] -arr [i-2]）;
}
for（int i = 0; i
printf（％lld\\\
，arr [p [i]]）;
}
return 0;
}
给定：qi适合64位整数。因为索引可以非常大，我不能声明一个数组，我应该如何处理这个问题（因为蛮力会给出TLE）。谢谢！
HA！ 't require（complete）iteration：
考虑一些值 Si 和 code>，其中 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，...， 0，...，5，.5，0，...
.1，1，.9，.1，.8，.7，.1，.6，.5，.1，.4， 3，.1，.2，.1，.1，0，...
到代码：只要一个值是 0 ，不需要更多的迭代，接下来的两个数字将与上一个相同，然后将再次有一个 0 等：
// A和B也可以为负，这不会改变算法，
//但是这种方式的实现更容易
uint64_t序列（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];
}
在此演示（如果您喜欢，可以使用 a 和 b 。
如果您重复查询同一个A和B，可以缓存所有值，直到 next == 0 在 std :: vector 中，为您提供以下查询的真正恒定时间。
确定在序列到达 0 之前有一个模式，但是我找不到它。
我只是注意到我错过了它应该是差异的绝对值...
如果它足够快，这里是一个迭代版本：
//决定具体的类型是很困难的...
uint64_t sequence 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 的下一个较低值开始，而不是从开始。当然，您还需要管理该地图：保持它小，并填充有用的值。
不是一个编程问题，它是一个算法。让我们看看序列的第一个数字：
a
b
ab
b- （2a-3b）= 5b-3a（ab）= 2b-a
（ab） - （b-
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 ）* a +
（-1）^（n-1）* fib（n）* b
$ b 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）
}
长序列（长A，长B，无符号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）;
}
某些现场演示在这里，但是当接近更大的数字时，这是有问题的（我怀疑纤维不正确）。
演示还包含序列的迭代版本，作为控件。如果这足够快你可以使用它。不需要存储任何超过最后两个数字。
为了进一步改善这一点，你可以使用一个查询表与斐波纳契数字，记住每十分之一（及其后继者）的序列号。
Problem statement[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 )
What I Tried(This would give a runtime error) :
#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!
HA! There is a solution that doesn't require (complete) iteration:
Considering some values Si and Sj, where i, j > 1. Then, looking at how the numbers of the sequence are built (using the absolute value), we can conclude that both numbers are positive.
Then the absolute value of their difference is guaranteed to be less (or equal) than the larger of the two.
Assuming it is strictly less than the larger of the two, within the next two steps, the larger value of the original values will go "out of scope". From that we can conclude that in this case, the numbers of the sequence are getting smaller and smaller.
(*) If the difference is equal to the larger one, then the other number must have been 0. In the next step, one of two things might happen:
a) The larger goes out of scope, then the next two numbers are the calculated difference (which is equal to the larger) and 0, which will yield again the larger value. Then we have the same situation as in ...
b) The zero goes out of scope. Then the next step will compute the difference between the larger and the calculated difference (which is equal to the larger), resulting in 0. In the next step, this leads back to the original (*) situation.
Result: A repeating pattern of L, L, 0, ...
Some examples:
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, ...
Applying that to the code: As soon as one value is 0, no more iteration is required, the next two numbers will be the same as the previous, then there will be again a 0 and so on:
// 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 (play with the a and b values if you like).
If you have repeated queries for the same A and B, you could cache all values until next == 0 in a std::vector, giving you really constant time for the following queries.
I'm also pretty sure that there's a pattern before the sequence reaches 0, but I wasn't able to find it.
I just noticed that I missed that it should be the absolute value of the difference ...
If it's fast enough, here is an iterative version:
// 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];
}
As you see you don't need to store all values, only the last two numbers are needed to compute the next one.
If this isn't fast enough you could add memorisation: Store the pairs of prev values in an ordered std::map (mapping n to those pairs). You can then start from the entry with the next, lower value of n instead of from the beginning. Of course you need to manage that map then, too: Keep it small and filled with "useful" values.
This is not a programming problem, it's an algorithmic one. Let's look at the first numbers of that sequence:
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
...
Looking only at the absolute value of the coefficients shows ...
b: 0 1 1 2 3 5 8 ...
a: (1) 0 1 1 2 3 5 ...
... that this is about the Fibonacci sequence. Then, there's also the sign, but this is pretty easy:
b: - + - + - ...
a: + - + - + ...
So the nth number in your sequence should be equal to
f(0) = a
f(n) = (-1)^n * fib(n-1) * a +
(-1)^(n-1) * fib(n) * b
Of course now we have to calculate the nth Fibonacci number, but fortunately there's already a solution for that:
fib(n) = (phi^n - chi^n) / (phi - chi)
with
phi = (1 + sqr(5)) / 2
chi = 1 - phi
So, bringing that to code:
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);
}
Some live demo is here, but this gets problematic when approaching larger numbers (I suspect the fib getting incorrect).
The demo contains also the iterative version of the sequence, as control. If that's fast enough for you, use that instead. No need to store anything more than the last two numbers.
To improve this further, you could use a lookup table with holes for the Fibonacci numbers, i.e. remembering every tenth (and their successor) number of the sequence.
这篇关于计算系列无法存储值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
