离散数学——冯诺依曼邻居问题

Problem:

Analysis:

递推问题从状态入手

容易发现在每一轮扩增时，扩增的来源细胞一定是上一轮的新增细胞。即有第\(n\)轮扩增时的来源细胞有\(T(n)-T(n-1)\)

接下来容易发现除上下两细胞外，所有的细胞可分为左右两部分，分别向左右扩增一个单位。上下两细胞又另外分别向四周扩增\(3\)个单位

于是有递推方程为\(T(n+1)-T(n)=T(n)-T(n-1)-2+6\)

显然可以得到一个二阶等差数列。

可以通过解非齐次线性方程或是待定系数法解之，这里因为形式特殊（二阶等差数列）故使用待定系数法

于是设\(T(n)=an^2+bn+c\)

将初始\(T(0)=1\),\(T(1)=5\),\(T(2)=13\)代入即可解得

\(T(n)=2n^2+2n+1\)

关于代码，则同样有两种解法，一种是\(O(1)\)的直接计算，另一种是\(O(n)\)的动态规划预处理，这里我们都提供。

其中两种方法均支持一万位以内的答案计算，但是递推法相对慢得多，不具有普适性

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2020-06-27 14:13:39
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : 离散数学——冯诺依曼邻居问题
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 10000, BASE = 1000000000, WIDTH = 9; //压位
char in[10005];
struct bigint
{
    ll element[maxn]; //用来存放每一位(元)
    ll len;
    bigint operator=(ll num) //从ll向bigint转换
    {
        memset(element, 0, sizeof(element));
        len = 0;
        while (num > 0)
        {
            element[len++] = num % BASE;
            num /= BASE;
        }
        return *this;
    }
    bigint operator=(const char *str) //从str向bigint转换
    {
        memset(element, 0, sizeof(element));
        ll num_len = strlen(str);
        len = (num_len + WIDTH - 1) / WIDTH;
        int pos = 0;
        for (int i = num_len - 1; pos < len; i -= WIDTH)
        {
            for (int j = 0; j < WIDTH; j++)
            {
                element[pos] += (str[i - j] - '0') * pow(10, j);
                if (i - j == 0)
                {
                    break;
                }
            }
            pos++;
        }
        return *this;
    }
    bool operator<(const bigint &b) const //bigint小于比较
    {
        if (b.len != len)
        {
            return len < b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] < b.element[i];
            }
        }
        return false;
    }
    bool operator<=(const bigint &b) const //bigint小于等于比较
    {
        if (b.len != len)
        {
            return len < b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] < b.element[i];
            }
        }
        return true;
    }
    bool operator>(const bigint &b) const //bigint大于比较
    {
        if (b.len != len)
        {
            return len > b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] > b.element[i];
            }
        }
        return false;
    }
    bool operator>=(const bigint &b) const //bigint大于等于比较
    {
        if (b.len != len)
        {
            return len > b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] > b.element[i];
            }
        }
        return true;
    }
    bool operator==(const bigint &b) const //bigint等于比较
    {
        if (b.len != len)
        {
            return false;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return false;
            }
        }
        return true;
    }
    bigint operator+(const bigint &b) const //bigint加法
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = len;
        for (int i = 0; i < len; i++)
        {
            ans.element[i] += element[i] + b.element[i]; //加
            if (ans.element[i] >= BASE)                  //如果多了就借位
            {
                ans.element[i + 1] += ans.element[i] / BASE;
                ans.element[i] %= BASE;
            }
        }
        ans.len++;
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    bigint operator-(const bigint &b) const //bigint减法
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = len;
        for (int i = 0; i < len; i++)
        {
            ans.element[i] += element[i] - b.element[i]; //减
            if (ans.element[i] < 0)                      //如果多了就借位
            {
                ans.element[i] += BASE;
                ans.element[i + 1]--;
            }
        }
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    bigint operator*(const bigint &b) const //bigint乘法
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = 2 * len;
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < b.len; j++)
            {
                ans.element[i + j] += element[i] * b.element[j]; //乘
                if (ans.element[i + j] >= BASE)                  //如果多了就借位
                {
                    ans.element[i + j + 1] += ans.element[i + j] / BASE;
                    int cur = i + j + 1;
                    while (ans.element[cur] >= BASE)
                    {
                        ans.element[cur + 1] += ans.element[cur] / BASE;
                        ans.element[cur] %= BASE;
                        cur++;
                    }
                    ans.element[i + j] %= BASE;
                }
            }
        }
        ans.len++;
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    bigint operator/(const ll &b) const //bigint除法 element len/b(先撸个半成品，这玩意儿太鬼畜了)
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = len;
        ans.element[len - 1] = (element[len - 1]) / b;
        ll lef = element[len - 1] % b;
        for (int i = len - 2; i >= 0; i--)
        {
            ans.element[i] = (element[i] + lef * BASE) / b;
            lef = (element[i] + lef * BASE) % b;
        }
        ans.len++;
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    void bigint_init()
    {
        memset(element, 0, sizeof(element));
        len = 0;
    }
    bool bigint_read()
    {
        memset(in, 0, sizeof(in));
        scanf("%s", in);
        // if (!(strlen(in) == 1 && in[0] == '0'))
        //     return false;
        *this = in;
        return true;
    }
    void bigint_print()
    {
        if (len == 0)
            printf("0");
        else
        {
            printf("%lld", element[len - 1]);
            for (int i = len - 2; i >= 0; i--)
            {
                printf("%09lld", element[i]);
            }
        } //注意输出的时候除了第一位其他不够位数都用0补齐(避免遗漏前缀0)
        printf("\n");
    }
};
int main()
{
    cout << "Please enter the target number: ";
    bigint maxm;
    maxm.bigint_init();
    maxm.bigint_read();

    bigint ans;
    ans.bigint_init();
    ans = maxm;

    bigint a;
    a.bigint_init();

    bigint b;
    b.bigint_init();

    bigint one;
    one.bigint_init();
    one = 1;

    bigint two;
    two.bigint_init();
    two = 2;

    a = ans * ans;
    a = a * two;
    b = ans * two;
    ans = a;
    ans = ans + b;
    if (ans < one)
    {
        ans = one + ans;
    }
    else
    {
        ans = ans + one;
    }
    cout << "The answer is: ";
    ans.bigint_print();
}

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2020-06-27 13:57:53
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : 离散数学——冯诺依曼邻居问题(dp算法)(slow)
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 10000, BASE = 1000000000, WIDTH = 9; //压位
char in[10005];
struct bigint
{
    ll element[maxn]; //用来存放每一位(元)
    ll len;
    bigint operator=(ll num) //从ll向bigint转换
    {
        memset(element, 0, sizeof(element));
        len = 0;
        while (num > 0)
        {
            element[len++] = num % BASE;
            num /= BASE;
        }
        return *this;
    }
    bigint operator=(const char *str) //从str向bigint转换
    {
        memset(element, 0, sizeof(element));
        ll num_len = strlen(str);
        len = (num_len + WIDTH - 1) / WIDTH;
        int pos = 0;
        for (int i = num_len - 1; pos < len; i -= WIDTH)
        {
            for (int j = 0; j < WIDTH; j++)
            {
                element[pos] += (str[i - j] - '0') * pow(10, j);
                if (i - j == 0)
                {
                    break;
                }
            }
            pos++;
        }
        return *this;
    }
    bool operator<(const bigint &b) const //bigint小于比较
    {
        if (b.len != len)
        {
            return len < b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] < b.element[i];
            }
        }
        return false;
    }
    bool operator<=(const bigint &b) const //bigint小于等于比较
    {
        if (b.len != len)
        {
            return len < b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] < b.element[i];
            }
        }
        return true;
    }
    bool operator>(const bigint &b) const //bigint大于比较
    {
        if (b.len != len)
        {
            return len > b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] > b.element[i];
            }
        }
        return false;
    }
    bool operator>=(const bigint &b) const //bigint大于等于比较
    {
        if (b.len != len)
        {
            return len > b.len;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return element[i] > b.element[i];
            }
        }
        return true;
    }
    bool operator==(const bigint &b) const //bigint等于比较
    {
        if (b.len != len)
        {
            return false;
        }
        for (int i = b.len - 1; i >= 0; i--)
        {
            if (b.element[i] != element[i])
            {
                return false;
            }
        }
        return true;
    }
    bigint operator+(const bigint &b) const //bigint加法
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = len;
        for (int i = 0; i < len; i++)
        {
            ans.element[i] += element[i] + b.element[i]; //加
            if (ans.element[i] >= BASE)                  //如果多了就借位
            {
                ans.element[i + 1] += ans.element[i] / BASE;
                ans.element[i] %= BASE;
            }
        }
        ans.len++;
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    bigint operator-(const bigint &b) const //bigint减法
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = len;
        for (int i = 0; i < len; i++)
        {
            ans.element[i] += element[i] - b.element[i]; //减
            if (ans.element[i] < 0)                      //如果多了就借位
            {
                ans.element[i] += BASE;
                ans.element[i + 1]--;
            }
        }
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    bigint operator*(const bigint &b) const //bigint乘法
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = 2 * len;
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < b.len; j++)
            {
                ans.element[i + j] += element[i] * b.element[j]; //乘
                if (ans.element[i + j] >= BASE)                  //如果多了就借位
                {
                    ans.element[i + j + 1] += ans.element[i + j] / BASE;
                    int cur = i + j + 1;
                    while (ans.element[cur] >= BASE)
                    {
                        ans.element[cur + 1] += ans.element[cur] / BASE;
                        ans.element[cur] %= BASE;
                        cur++;
                    }
                    ans.element[i + j] %= BASE;
                }
            }
        }
        ans.len++;
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    bigint operator/(const ll &b) const //bigint除法 element len/b(先撸个半成品，这玩意儿太鬼畜了)
    {
        bigint ans;
        memset(ans.element, 0, sizeof(ans.element));
        ans.len = len;
        ans.element[len - 1] = (element[len - 1]) / b;
        ll lef = element[len - 1] % b;
        for (int i = len - 2; i >= 0; i--)
        {
            ans.element[i] = (element[i] + lef * BASE) / b;
            lef = (element[i] + lef * BASE) % b;
        }
        ans.len++;
        while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
        {
            ans.len--;
        }
        return ans;
    }
    void bigint_init()
    {
        memset(element, 0, sizeof(element));
        len = 0;
    }
    bool bigint_read()
    {
        memset(in, 0, sizeof(in));
        scanf("%s", in);
        // if (!(strlen(in) == 1 && in[0] == '0'))
        //     return false;
        *this = in;
        return true;
    }
    void bigint_print()
    {
        if (len == 0)
            printf("0");
        else
        {
            printf("%lld", element[len - 1]);
            for (int i = len - 2; i >= 0; i--)
            {
                printf("%09lld", element[i]);
            }
        } //注意输出的时候除了第一位其他不够位数都用0补齐(避免遗漏前缀0)
        printf("\n");
    }
};
int main()
{
    cout << "Please enter the target number: ";
    ll maxm;
    cin >> maxm;
    bigint a;
    a.bigint_init();
    a = 1;
    bigint b;
    b.bigint_init();
    b = 5;
    bigint c;
    c.bigint_init();

    bigint q;
    q.bigint_init();
    q = 2;
    bigint w;
    w.bigint_init();
    w = 4;
    for (ll i = 2; i <= maxm; i++)
    {
        if (i % 3 == 2)
        {
            c = b * q;
            c = c - a;
            c = c + w;
        }
        else if (i % 3 == 0)
        {
            a = c * q;
            a = a - b;
            a = a + w;
        }
        else
        {
            b = a * q;
            b = b - c;
            b = b + w;
        }
    }
    cout << "The answer is: ";
    if (maxm % 3 == 0)
    {
        a.bigint_print();
    }
    else if (maxm % 3 == 1)
    {
        b.bigint_print();
    }
    else
    {
        c.bigint_print();
    }
}