交替横竖折叠纸张N次后切割的纸片总数计算问题求解

核心思路 #

我们可以将两个方向的折叠影响独立计算：

• 任意方向折叠k次后，沿该方向切一刀，展开后该方向会被分成 2^k +1 片：每次折叠会让该方向的纸张层数翻倍，一刀会同时切开所有层，展开后对应2^k道切痕，切痕数+1就是分片数。
• 题目中N次操作按「竖向→横向→竖向→…」交替进行，因此：
  • 竖向折叠总次数：a = (N + 1) // 2
  • 横向折叠总次数：b = N // 2
• 最终总纸片数是两个方向分片数的乘积，结果对 10^9+7 取模即可，公式为：
  总数量 = (2^a + 1) * (2^b + 1) mod 10^9+7

验证测试用例 #

所有测试用例完全匹配推导结果：

• N=0：a=0，b=0 → (1+1)*(1+1)=4 ✔️
• N=1：a=1，b=0 → (2+1)*(1+1)=6 ✔️
• N=2：a=1，b=1 → (2+1)*(2+1)=9 ✔️
• N=3：a=2，b=1 → (4+1)*(2+1)=15 ✔️

代码实现（Python） #

MOD = 10**9 + 7
def calculate_pieces(N):
    a = (N + 1) // 2
    b = N // 2
    pow_a = pow(2, a, MOD)
    pow_b = pow(2, b, MOD)
    return (pow_a + 1) * (pow_b + 1) % MOD

该实现时间复杂度为O(logN)（由快速幂计算决定），完全满足N≤1e5的性能要求。

内容的提问来源于stack exchange，提问作者Anand