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();
}
}
噜噜噜噜噜噜噜