问求解递归关系，其中偶数和奇数值之间存在单独的关系

EN

看看这个问题，因为你会被要求

• 多次评估复发
• 对于非常大的输入，

你很可能需要

• 找到一个封闭形式的复发解决方案，或
• 找到一种方法来评估次线性时间内第n个重复项。

现在的问题是如何做到这一点。让我们来看看重现，定义为

• f（1）= f（2）= 1，
• 如果n是奇数，则f（n + 2）= 3f（n）
• 如果n是偶数，则f（n + 2）= 2f（n + 1）-f（n）+ 2。

让我们从探索重复发现开始，看看是否出现任何模式。在这里突出的东西 - 这种复发的奇怪术语仅取决于复发中的其他奇数术语。这意味着我们可以想象试图将这种重复分为两个较小的重复：一个纯粹处理奇数项，一个纯粹处理偶数项。设D（n）为奇项的序列，E（n）为偶数项的序列。然后我们有

• D（1）= 1
• D（n + 2）= 3D（n）

我们只需要对奇数进行D评估，因此我们可以使用它来查看模式是否出现：

• D（2·0 + 1）= 1 = 3 0
• D（2·1 + 1）= 3 = 3 1
• D（2·2 + 1）= 9 = 3 2
• D（2·3 + 1）= 27 = 3 3

这里的模式是D（2n + 1）= 3 n。嘿，这是个好消息！这意味着我们有一种直接计算D（2n + 1）的方法。

考虑到这一点，请注意E（n）定义为

• E（2）= 1 = D（1）
• E（n + 2）= 2D（n + 1）-E（n）+ 2

请记住，我们知道D（n + 1）的确切值，这将使我们的生活变得更加容易。让我们看看如果我们稍微重复这个重复发生会发生什么。例如，请注意

和（8） = 2D（7） - E（6）+ 2 = 2D（7）+ 2 - （2D（5） - E（4）+ 2） = 2D（7） - 2D（5）+ E（4） = 2D（7） - 2D（5）+（2D（3） - E（2）+ 2） = 2D（7） - 2D（5）+ 2D（3）+ 2 - D（1） = 2D（7）-2D（5）+ 2D（3）-D（1）+ 2

好的......那真的非常有趣。似乎我们得到了D重复的交替总和，我们在包括和排除2之间交替。在这一点上，如果我不得不猜测，我会说解决这种复发的方法是考虑将偶数情况进一步细分为输入对于偶数n为2n而对于奇数n为2n的情况。事实上，请注意，如果偶数n的输入是2n，那么最后将没有+2项（所有+ 2都被-2平衡），而如果输入是奇数，那么将会最后是一个+2个词（所有的+ 2都被-2平衡）。

现在，让我们转向问题的另一个方面。您没有被要求查询重复的个别条款。您被要求查询重复的总和，并通过一系列输入进行评估。我们在这里获得D项的交替和差异的事实真的非常有趣。例如，什么是f（10）+ f（11）+ f（12）？好吧，我们知道f（11）= D（11），我们可以直接计算。而且我们也知道f（10）和f（12）是E（10）和E（12）。并观察如果我们评估E（10）+ E（12）会发生什么：

E（10）+ E（12） =（D（9） - D（7）+ D（5） - D（3）+ D（1）+ 2）+（D（11） - D（9）+ D（7） - D（5） + D（3） - D（1）） = D（11）+（D（9） - D（9））+（D（7） - D（7））+（D（5） - D（5））+（D（3） - D（ 3））+（D（1） - D（1））+ 2 = D（11）+ 2。

现在这很有趣。请注意，除D（11）术语和+2术语外，所有术语都已取消！更一般地说，这可能会让我们猜测有关如何简化E（n + 2）+ E（n）的一些规则。事实上，有。特别：

E（2n）+ E（2n + 2）= D（2n + 1）+ 2

这意味着如果我们在一个范围内总结许多连续值，那么每对相邻的偶数项将立即简化为D（2n + 1）+ 2形式的某些形式。

还有一些工作要做。例如，您需要能够总结大量的D（n）项，并且您需要考虑所有+2项的影响。我会把这些留给你弄清楚。

一个提示：要求您返回的所有值都是模数P.这意味着值0，D（1），D（1）+ D（3），D（1）+ D（3）的序列）+ D（5），D（1）+ D（3）+ D（5）+ D（7）等最终必须再次达到0（mod P）。您可以计算在此之前必须发生的术语数量，并通过仅显式计算这些值来记下执行此操作时遇到的所有值。这将使您能够连续汇总大量连续的D项 - 您可以按周期长度修改项数，然后在表中查找剩余总和。

希望这可以帮助！