计算纸片总数

Question

下面是一道面试题，我答不出来，需要一些帮助。

问题：

一个人在玩纸，在他的游戏过程中，他将纸垂直折叠一圈，然后再水平折叠一圈，并重复此过程 n 次。完成后，他将纸张垂直和水平切割。手头的任务是将一个数字“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 (top left),b (top Right) ,c (bottom left) ,d (bottom Right))

同样为了一致性和理解，我们总是在垂直折叠中从右向左折叠（右半部分在左半部分之上），在水平折叠中从下到上折叠（下半部分在顶部之上）一半），我们从水平开始作为我们将预成型的第一个折叠。

首先我们从每个角的 1 开始，所以当我们划分时我们得到所有角的总和，如下所示：

(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) when you fold vertically (from right to left)

和

(a,b,c,d) -> (a+c,b+d,a,b) when you fold horizontally (from bottom to top)

所以你可以获得递归关系，这里有一些简单的 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);
}

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

计算纸片总数

Counting total number of paper pieces

algorithm

data-structures

adhoc

number-theory