如何将n个数字相加，相乘到数组中的给定范围，并以O（n）时间反转数组中的范围？

这个答案很长，但是恕我直言，我已经以相当容易理解的方式编写了它，并做了很多解释，所以请耐心等待一下。

O(N)假设A和B均为整数，可以及时解决此问题。否则，您可以在此时停止阅读。但是我认为有必要将算法分解为几个不同的步骤，每个步骤都是O(N)。因此，它将仍然是O(N)整体。

问题的最困难部分可能是弄清楚如何使此步骤以线性时间运行：

    if ith letter of S is 'R'
        reverse L[i...N]

如果我们只是盯着原始算法，我们将确信，即使其他步骤可以在线性时间内完成，该步骤也永远不可能在线性时间内完成。但这是不正确的。我们该怎么做呢？我想到的方法是从双头队列/双端队列数据结构中借用一个想法。由于我们知道数组的L长度，因此我们只需维护3个变量leftmost，rightmost和isReversed。

• leftmost将保留该L数组当前最左边的未使用索引，因此leftmost被初始化为1，因为我们使用的是您的问题中所述的一个索引数组（术语“未使用”将在后面说明）。
• rightmost将保存L数组当前最右边的未使用索引，并因此初始化为N的长度L。
• isReversed用于指示数组是否被反转。初始化为false。

我们要做的第一个任务是在应用L所有reverse操作后找出数组原始元素的最终顺序。为了达到与反转相同的效果，甚至不需要反转阵列。这可以通过遍历输入字符串S一次，并找出L所有反向操作后数组的哪个元素应位于每个位置来完成。为简单起见，我们创建了一个新的整数数组L'，该数组将L在应用所有反向操作后保留的最终原始元素，并尝试填充L'。

假设我们在索引处i，并且S[i] == 'R'，所以我们设置isReversed = true要表明我们正在反转子数组[i..N]。当时isReversed == true，我们知道子[i..N]数组将被反转，因此位于的元素L'[i]应该是最右边的未使用元素，其索引为rightmost。因此，我们设置了L'[i] = L[rightmost]，并减 rightmost了1（rightmost = rightmost - 1）。相反，如果isReversed == false我们不反转子[i..N]数组，则at处的元素L'[i]应该是最左边的未使用元素，其索引为leftmost。因此，我们设定L'[i] = L[leftmost]和增量 leftmost由1（leftmost = leftmost - 1）。随后reverse的值将取反isReversed。

因此，当前的算法在C ++中看起来像这样（我假设您对C ++没问题，因为您的问题标记之一是C ++）：

// set up new array L'
int Lprime[N+1];
int leftmost = 1;
int rightmost = N;
bool isReversed = false;

for (int i = 1; i <= N; i++) {
    if (S[i] == 'R') {
        // negate isReversed
        isReversed = !isReversed;
    }

    if (isReversed) {
        Lprime[i] = L[rightmost];
        rightmost = rightmost - 1;
    } else {
        Lprime[i] = L[leftmost];
        leftmost = leftmost + 1;
    }
}

请确认这是正确的，尽管我认为是正确的。

现在，我们看一下原始算法的其余部分：

    else if ith letter of S is 'A'
        add A to all numbers of L[i..N].
    else if ith letter of S is 'M'
        multiply B to all numbers of L[i..N].

    for all number in L[i..N], module them by C.

困难的部分似乎是需要对每个索引C在子数组上执行模运算。但是基于我的有限理解，这是模运算，我们真的不需要在每个子数组的子数组上执行它。但是，请不要相信我。我对数论的理解非常初级。[i..N]i[i..N]i

不仅如此，加法和乘法的步骤也可以简化。这里的技巧是维护2个额外的变量，我们将它们称为multiplicativeFactor和additiveConstant。multiplicativeFactor用来保持一个常数，我们需要乘以L'[i]。最初是这样1。该additiveConstant变量，顾名思义，是用来存放我们需要添加到任何恒定L'[i]的倍增后L'[i]的multiplicativeFactor完成。additiveConstant是不合理的0。

要看到这个更具体的方式，让我们设置A = 3，B = 5。并假设S是字符串"AMMAAM"。这意味着以下含义（注意：我们暂时不考虑模数C）：

• 在索引处1，设置L'[1] = L'[1] + 3;
• 在索引处2，设置L'[2] = (L'[2] + 3) * 5;
• 在索引处3，设置L'[3] = ((L'[3] + 3) * 5) * 5;
• 在索引处4，设置L'[4] = (((L'[4] + 3) * 5) * 5) + 3;
• 在索引处5，设置L'[5] = ((((L'[5] + 3) * 5) * 5) + 3) + 3
• 在索引处6，设置L'[6] = (((((L'[6] + 3) * 5) * 5) + 3) + 3) * 5

观察先前字符的影响'A'并'M'“继承”（或级联）到的未来元素中L'。让我们稍微表达一下这些操作：

• L'[1] = L'[1] + 3
• L'[2] = 5 * L'[2] + (3 * 5)
• L'[3] = 5 * 5 * L'[3] + (3 * 5 * 5)
• L'[4] = 5 * 5 * L'[4] + (3 * 5 * 5 + 3)
• L'[5] = 5 * 5 * L'[5] + (3 * 5 * 5 + 3 + 3)
• L'[6] = 5 * 5 * 5 * L'[6] + (3 * 5 * 5 + 3 + 3) * 5

我们开始看到一些模式。

• 的乘法因子L'[i]始终是的幂B。添加A对该倍增因子没有任何影响。乘法因子存储在multiplicativeConstant我们上面描述的变量中
• 每次我们需要乘以L'[i]一个额外的B乘积时，都需要乘以所有的常数（由加法产生的A）乘以B以获得要加到的最终常数L'[i]。这就是上述additiveConstant变量的目的。
• 的乘积L'[i]应在additiveConstant加到之前完成L'[i]

因此，每个的最终值都L'[i]可以表示为multiplicativeConstant * L'[i] + additiveConstant;，并且算法的第二个主要部分看起来像这样：

int multiplicativeConstant = 1;
int additiveConstant = 0;
for (int i = 1; i <= N; i++) {
    if (S[i] == 'A') {
        additiveConstant += A;
    } else if (S[i] == 'M') {
        multiplicativeConstant *= B;
        // need to multiply all the constants by B as well
        additiveConstant *= B;
    }
    Lprime[i] = multiplicativeConstant * Lprime[i] + additiveConstant;
}

我没有谈论过一个警告。整数溢出的multiplicativeConstant和additiveConstant，与中间计算一起。如果L是int数组，那么我们很幸运，因为我们可以使用long long所有内容并避免溢出。否则，我们必须注意中间计算不会溢出。

现在该怎么modulo C办？实际上，它们在那里使每个值都L'[i]在该范围内[0..C-1]。基于我对数论的有限理解，我们可以像这样执行模运算以达到相同的效果：

int multiplicativeConstant = 1;
int additiveConstant = 0;
for (int i = 1; i <= N; i++) {
    if (S[i] == 'A') {
        additiveConstant = (additiveConstant + (A % C)) % C;
    } else if (S[i] == 'M') {
        multiplicativeConstant = (multiplicativeConstant * (B % C)) % C;
        // need to multiply all the constants by B as well
        additiveConstant = (additiveConstant * (B % C)) % C;
    }
    Lprime[i] = ((multiplicativeConstant * (Lprime[i] % C)) % C + additiveConstant) % C;
}

这解决了multiplicativeConstant和additiveConstant变量的溢出问题（但并不能防止中间计算和其他变量的溢出），并完善了我们的算法。我相信这是正确的，但是请您自己验证。我无法解释模块化算术知识，因为我只知道如何使用它，因此您将不得不自己查找它。顺便说一句，A % C和B % C零件可以一次完成，其结果存储在变量中。

最后，将所有内容放在一起：

// set up new array L'
int Lprime[N+1];
int leftmost = 1;
int rightmost = N;
bool isReversed = false;

for (int i = 1; i <= N; i++) {
    if (S[i] == 'R') {
        // negate isReversed
        isReversed = !isReversed;
    }

    if (isReversed) {
        Lprime[i] = L[rightmost];
        rightmost = rightmost - 1;
    } else {
        Lprime[i] = L[leftmost];
        leftmost = leftmost - 1;
    }
}

int multiplicativeConstant = 1;
int additiveConstant = 0;
// factor out A % C and B % C
int aModC = A % C;
int bModC = B % C;
for (int i = 1; i <= N; i++) {
    if (S[i] == 'A') {
        additiveConstant = (additiveConstant + aModC) % C;
    } else if (S[i] == 'M') {
        multiplicativeConstant = (multiplicativeConstant * bModC) % C;
        // need to multiply all the constants by B as well
        additiveConstant = (additiveConstant * bModC) % C;
    }
    Lprime[i] = ((multiplicativeConstant * (Lprime[i] % C)) % C + additiveConstant) % C;
}
// print Lprime

O(N)总体而言，这是及时的。

再一次，如果您担心整数溢出（假设它L是一个int数组），则可以将其long long用于计算中涉及的所有变量，那应该没问题。