c++ - 查找递归修改正方形的周长

Question

我有一个边长为 1 的正方形。现在，每一秒后，边长为 L 的每个方 block 将分成四个边长为 L/2 的方 block 。

我需要计算所得图形的总周长，其中总周长定义为所得图形中所有线段的长度之和。例如，左侧图像的总周长为 4L，而右侧图像的总周长为 6L - 4L 从规则的正方形边缘和2L 来自内部线段。

我的代码:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod 1000000007

int main() {



        int s;
        cin>>s;
       long long  int ans=4;

        for(int i=1;i<=s;i++)
            ans+=1<<i;
            ans=ans%mod;

        cout<<ans<<endl;


    return 0;
}

由于最终答案可能不适合 64 位有符号整数，我需要计算答案模 1000000007。

例如0秒后，长度为4。1 秒后，长度为 6。我没有得到正确的输出。请帮忙

Answer 1

递归求解 - 让P(L, n)是 n 之后得到的图形的“周长”迭代，以 LxL 开始正方形。所以，P(L, n+1) = 4*P(L/2,n) - 2*L .此外，由于周长是线性的，P(L/2, n) = P(L, n)/2 , 给你 P(L,n) = 2*P(L,n-1) - 2*L .替代L=1并运行你的循环。

   int s;
   cin>>s;
   long long  int ans=4;

   for(int i=1;i<=s;i++)
   {
        ans = 2*(ans-1);
        ans=ans%mod;
   }