我正在解决一个无法理解的问题。我想出了自己的解决方案,但是不被接受:
N + 1个数字从A0到AN顺序出现(一次一个)。每个数字都可以放在最后一个序列的两侧。此时的分数将是该数字与其邻居的乘积,例如:A0.A1.A2或A2.A0.A1(A2可以放在A0.A1的任一侧,因此分数可以是A1.A2或A2。 A0;在A2出现之前也可能存在A1.A0)。我们需要总结所有可能组合中的所有可能分数;即第一个序列在N + 1个数字上的得分总和,然后在其他序列上的总和,依此类推,最后是所有这些总和的总和。
这是被认为可以接受的逻辑:
int pwr[0] = 1;
for (int i = 1; i < 100000; i++)
pwr[i] = (pwr[i - 1] << 1) % MOD;
extra = A0 * 2;
sum = 0;
for (int i = 1; i <= N; i++){
Ai = scan();
sum = (sum * 2 + Ai * extra) % MOD; //Mod is a scaling factor
extra = (extra + pwr[i] * Ai) % MOD;
}
有人可以解释这是如何工作的吗?
这是我针对相同问题的逻辑(解决方案),但未接受:
#include <iostream>
#include <cmath>
int main()
{
int T;
std::cin>>T;
long long int output[T];
for (int i = 0; i < T; ++i)
{
int N;
std::cin>>N;
long long int inp[N+1];
for (int j = 0; j <= N; ++j)
{
std::cin>>inp[j];
}
long long int tot = 0;
for (int j = 0; j < N; ++j)
{
for (int k = j+1; k <= N; ++k)
{
tot += (inp[j] * inp[k] * pow(2,N-k+1));
}
}
long long int num = pow(10,9) + 7;
output[i] = tot % num;
}
for (int i = 0; i < T; ++i)
{
std::cout<<output[i]<<std::endl;
}
return 0;
}
最佳答案
说明
在循环的每次迭代开始时,我相信:
sum
表示元素0..i-1 extra
表示元素0..i-1的所有排列的两个边缘元素的总和另请注意,元素0..i有
pow[i]=2^i
排列。在开始时,唯一的排列是[A0],其总和为0,并且总边缘为2.A0,因为A0在左边缘和右边缘上。
在迭代i中,我们通过考虑Ai在左侧的所有对象和Ai在右侧的所有对象,将排列的数量加倍。因此,这些排列的内部得分是
2*sum
,考虑边缘采样的额外得分是Ai*extra
。同样,对于所有
extra
排列,2^i
也需要增加Ai,因为它在每个新排列中位于左侧还是右侧。例
考虑[A0,A1,A2]。
有四种可能的方式来建立序列:
总分为4A0.A1 + 2A1.A2 + 2A2.A0