数纸片总数

Question

以下是我无法解决的面试问题，需要帮助。

问题：

一个人在玩纸，在他的游戏中，他在一个回合中垂直折叠纸张，然后在另一个回合中水平折叠，并重复这个过程多次。做完后，他把纸垂直地和水平地剪开。手边的任务是以一个数字"N“作为输入，并根据上面提到的模式，找到剪纸后在垂直和水平方向上将纸张折n次后的纸片数量。

Constraints:

1< N <10^5

N : Total number of turns
As the answer can be very large output the result mod 10^9+7

测试用例

Input: 0
Output: 4

Input: 1
Output: 6

Input: 2
Output: 9

Input: 3
Output: 15

我试图找到一些数字模式，但找不到，而且这个问题似乎与任何算法无关，因此我无法找到任何正确的方法。请帮我提出一些建议。

Answer 1

正如注释所提到的，您应该在部分(4个角落)中寻找一个模式，而不是在整个部分中。我们将将这些角点枚举为如下向量：

(a (左上角)，b(右上)，c(左下角)，d(右下角))

同时，为了一致性和理解，我们总是从右到左的垂直褶皱(左上半身的右上半)和水平褶皱的自下而上(上半部分的上半部分)，我们从水平开始，作为第一个褶皱，我们将预先形成。

首先，我们从每个角落的1开始，所以当我们除法时，我们得到所有角的和，如下：

(1，1，1)=1+1+1+1=4 (n = 0)

让我们看看每一个角落在几次跑步后会发生什么：

2，1，2，1) =2+1+2+1=6 (n =1)

(4,2,2,1) =4+2+2+1=9 (n = 2)

(6,3,4,2) =6+3+4+2= 15 (n = 3)

(9,6,6,4) =9+6+6+4= 25 (n = 4)

也许一开始很难看出两者之间的关系，但实际上模式非常简单：

(a，b，c，d) -> (a+b，a，c+d，c)当你垂直折叠时(从右到左)

和

(a，b，c，d) -> (a+c，b+d，a，b)当你水平折叠时(从下到上)

因此，您可以得到递归关系，下面是C中的一些简单代码：

int func(int a, int b, int c, int d, int n) {
 if (n == 0) return (a + b + c + d);
 if (n % 2 == 0) return func(a + b, a, c + d, c, n - 1);
 else return func(a + c, b + d, a, b, n - 1);
}

从这里你可以得到更好的计算结果，但这是一个开始。