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

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

/ 1评 / 5125次 / 5赞

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)\)的动态规划预处理，这里我们都提供。

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

  1. /*
  2. * @Author : Gehrychiang
  3. * @LastEditTime : 2020-06-27 14:13:39
  4. * @Website : www.yilantingfeng.site
  5. * @E-mail : gehrychiang@aliyun.com
  6. * @ProbTitle : 离散数学——冯诺依曼邻居问题
  7. */
  8. //#pragma GCC optimize(2)
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  12. const ll maxn = 10000, BASE = 1000000000, WIDTH = 9; //压位
  13. char in[10005];
  14. struct bigint
  15. {
  16. ll element[maxn]; //用来存放每一位(元)
  17. ll len;
  18. bigint operator=(ll num) //从ll向bigint转换
  19. {
  20. memset(element, 0, sizeof(element));
  21. len = 0;
  22. while (num > 0)
  23. {
  24. element[len++] = num % BASE;
  25. num /= BASE;
  26. }
  27. return *this;
  28. }
  29. bigint operator=(const char *str) //从str向bigint转换
  30. {
  31. memset(element, 0, sizeof(element));
  32. ll num_len = strlen(str);
  33. len = (num_len + WIDTH - 1) / WIDTH;
  34. int pos = 0;
  35. for (int i = num_len - 1; pos < len; i -= WIDTH)
  36. {
  37. for (int j = 0; j < WIDTH; j++)
  38. {
  39. element[pos] += (str[i - j] - '0') * pow(10, j);
  40. if (i - j == 0)
  41. {
  42. break;
  43. }
  44. }
  45. pos++;
  46. }
  47. return *this;
  48. }
  49. bool operator<(const bigint &b) const //bigint小于比较
  50. {
  51. if (b.len != len)
  52. {
  53. return len < b.len;
  54. }
  55. for (int i = b.len - 1; i >= 0; i--)
  56. {
  57. if (b.element[i] != element[i])
  58. {
  59. return element[i] < b.element[i];
  60. }
  61. }
  62. return false;
  63. }
  64. bool operator<=(const bigint &b) const //bigint小于等于比较
  65. {
  66. if (b.len != len)
  67. {
  68. return len < b.len;
  69. }
  70. for (int i = b.len - 1; i >= 0; i--)
  71. {
  72. if (b.element[i] != element[i])
  73. {
  74. return element[i] < b.element[i];
  75. }
  76. }
  77. return true;
  78. }
  79. bool operator>(const bigint &b) const //bigint大于比较
  80. {
  81. if (b.len != len)
  82. {
  83. return len > b.len;
  84. }
  85. for (int i = b.len - 1; i >= 0; i--)
  86. {
  87. if (b.element[i] != element[i])
  88. {
  89. return element[i] > b.element[i];
  90. }
  91. }
  92. return false;
  93. }
  94. bool operator>=(const bigint &b) const //bigint大于等于比较
  95. {
  96. if (b.len != len)
  97. {
  98. return len > b.len;
  99. }
  100. for (int i = b.len - 1; i >= 0; i--)
  101. {
  102. if (b.element[i] != element[i])
  103. {
  104. return element[i] > b.element[i];
  105. }
  106. }
  107. return true;
  108. }
  109. bool operator==(const bigint &b) const //bigint等于比较
  110. {
  111. if (b.len != len)
  112. {
  113. return false;
  114. }
  115. for (int i = b.len - 1; i >= 0; i--)
  116. {
  117. if (b.element[i] != element[i])
  118. {
  119. return false;
  120. }
  121. }
  122. return true;
  123. }
  124. bigint operator+(const bigint &b) const //bigint加法
  125. {
  126. bigint ans;
  127. memset(ans.element, 0, sizeof(ans.element));
  128. ans.len = len;
  129. for (int i = 0; i < len; i++)
  130. {
  131. ans.element[i] += element[i] + b.element[i]; //加
  132. if (ans.element[i] >= BASE) //如果多了就借位
  133. {
  134. ans.element[i + 1] += ans.element[i] / BASE;
  135. ans.element[i] %= BASE;
  136. }
  137. }
  138. ans.len++;
  139. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  140. {
  141. ans.len--;
  142. }
  143. return ans;
  144. }
  145. bigint operator-(const bigint &b) const //bigint减法
  146. {
  147. bigint ans;
  148. memset(ans.element, 0, sizeof(ans.element));
  149. ans.len = len;
  150. for (int i = 0; i < len; i++)
  151. {
  152. ans.element[i] += element[i] - b.element[i]; //减
  153. if (ans.element[i] < 0) //如果多了就借位
  154. {
  155. ans.element[i] += BASE;
  156. ans.element[i + 1]--;
  157. }
  158. }
  159. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  160. {
  161. ans.len--;
  162. }
  163. return ans;
  164. }
  165. bigint operator*(const bigint &b) const //bigint乘法
  166. {
  167. bigint ans;
  168. memset(ans.element, 0, sizeof(ans.element));
  169. ans.len = 2 * len;
  170. for (int i = 0; i < len; i++)
  171. {
  172. for (int j = 0; j < b.len; j++)
  173. {
  174. ans.element[i + j] += element[i] * b.element[j]; //乘
  175. if (ans.element[i + j] >= BASE) //如果多了就借位
  176. {
  177. ans.element[i + j + 1] += ans.element[i + j] / BASE;
  178. int cur = i + j + 1;
  179. while (ans.element[cur] >= BASE)
  180. {
  181. ans.element[cur + 1] += ans.element[cur] / BASE;
  182. ans.element[cur] %= BASE;
  183. cur++;
  184. }
  185. ans.element[i + j] %= BASE;
  186. }
  187. }
  188. }
  189. ans.len++;
  190. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  191. {
  192. ans.len--;
  193. }
  194. return ans;
  195. }
  196. bigint operator/(const ll &b) const //bigint除法 element len/b(先撸个半成品，这玩意儿太鬼畜了)
  197. {
  198. bigint ans;
  199. memset(ans.element, 0, sizeof(ans.element));
  200. ans.len = len;
  201. ans.element[len - 1] = (element[len - 1]) / b;
  202. ll lef = element[len - 1] % b;
  203. for (int i = len - 2; i >= 0; i--)
  204. {
  205. ans.element[i] = (element[i] + lef * BASE) / b;
  206. lef = (element[i] + lef * BASE) % b;
  207. }
  208. ans.len++;
  209. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  210. {
  211. ans.len--;
  212. }
  213. return ans;
  214. }
  215. void bigint_init()
  216. {
  217. memset(element, 0, sizeof(element));
  218. len = 0;
  219. }
  220. bool bigint_read()
  221. {
  222. memset(in, 0, sizeof(in));
  223. scanf("%s", in);
  224. // if (!(strlen(in) == 1 && in[0] == '0'))
  225. // return false;
  226. *this = in;
  227. return true;
  228. }
  229. void bigint_print()
  230. {
  231. if (len == 0)
  232. printf("0");
  233. else
  234. {
  235. printf("%lld", element[len - 1]);
  236. for (int i = len - 2; i >= 0; i--)
  237. {
  238. printf("%09lld", element[i]);
  239. }
  240. } //注意输出的时候除了第一位其他不够位数都用0补齐(避免遗漏前缀0)
  241. printf("\n");
  242. }
  243. };
  244. int main()
  245. {
  246. cout << "Please enter the target number: ";
  247. bigint maxm;
  248. maxm.bigint_init();
  249. maxm.bigint_read();
  251. bigint ans;
  252. ans.bigint_init();
  253. ans = maxm;
  255. bigint a;
  256. a.bigint_init();
  258. bigint b;
  259. b.bigint_init();
  261. bigint one;
  262. one.bigint_init();
  263. one = 1;
  265. bigint two;
  266. two.bigint_init();
  267. two = 2;
  269. a = ans * ans;
  270. a = a * two;
  271. b = ans * two;
  272. ans = a;
  273. ans = ans + b;
  274. if (ans < one)
  275. {
  276. ans = one + ans;
  277. }
  278. else
  279. {
  280. ans = ans + one;
  281. }
  282. cout << "The answer is: ";
  283. ans.bigint_print();
  284. }
/*
 * @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();
}
  1. /*
  2. * @Author : Gehrychiang
  3. * @LastEditTime : 2020-06-27 13:57:53
  4. * @Website : www.yilantingfeng.site
  5. * @E-mail : gehrychiang@aliyun.com
  6. * @ProbTitle : 离散数学——冯诺依曼邻居问题(dp算法)(slow)
  7. */
  8. //#pragma GCC optimize(2)
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  12. const ll maxn = 10000, BASE = 1000000000, WIDTH = 9; //压位
  13. char in[10005];
  14. struct bigint
  15. {
  16. ll element[maxn]; //用来存放每一位(元)
  17. ll len;
  18. bigint operator=(ll num) //从ll向bigint转换
  19. {
  20. memset(element, 0, sizeof(element));
  21. len = 0;
  22. while (num > 0)
  23. {
  24. element[len++] = num % BASE;
  25. num /= BASE;
  26. }
  27. return *this;
  28. }
  29. bigint operator=(const char *str) //从str向bigint转换
  30. {
  31. memset(element, 0, sizeof(element));
  32. ll num_len = strlen(str);
  33. len = (num_len + WIDTH - 1) / WIDTH;
  34. int pos = 0;
  35. for (int i = num_len - 1; pos < len; i -= WIDTH)
  36. {
  37. for (int j = 0; j < WIDTH; j++)
  38. {
  39. element[pos] += (str[i - j] - '0') * pow(10, j);
  40. if (i - j == 0)
  41. {
  42. break;
  43. }
  44. }
  45. pos++;
  46. }
  47. return *this;
  48. }
  49. bool operator<(const bigint &b) const //bigint小于比较
  50. {
  51. if (b.len != len)
  52. {
  53. return len < b.len;
  54. }
  55. for (int i = b.len - 1; i >= 0; i--)
  56. {
  57. if (b.element[i] != element[i])
  58. {
  59. return element[i] < b.element[i];
  60. }
  61. }
  62. return false;
  63. }
  64. bool operator<=(const bigint &b) const //bigint小于等于比较
  65. {
  66. if (b.len != len)
  67. {
  68. return len < b.len;
  69. }
  70. for (int i = b.len - 1; i >= 0; i--)
  71. {
  72. if (b.element[i] != element[i])
  73. {
  74. return element[i] < b.element[i];
  75. }
  76. }
  77. return true;
  78. }
  79. bool operator>(const bigint &b) const //bigint大于比较
  80. {
  81. if (b.len != len)
  82. {
  83. return len > b.len;
  84. }
  85. for (int i = b.len - 1; i >= 0; i--)
  86. {
  87. if (b.element[i] != element[i])
  88. {
  89. return element[i] > b.element[i];
  90. }
  91. }
  92. return false;
  93. }
  94. bool operator>=(const bigint &b) const //bigint大于等于比较
  95. {
  96. if (b.len != len)
  97. {
  98. return len > b.len;
  99. }
  100. for (int i = b.len - 1; i >= 0; i--)
  101. {
  102. if (b.element[i] != element[i])
  103. {
  104. return element[i] > b.element[i];
  105. }
  106. }
  107. return true;
  108. }
  109. bool operator==(const bigint &b) const //bigint等于比较
  110. {
  111. if (b.len != len)
  112. {
  113. return false;
  114. }
  115. for (int i = b.len - 1; i >= 0; i--)
  116. {
  117. if (b.element[i] != element[i])
  118. {
  119. return false;
  120. }
  121. }
  122. return true;
  123. }
  124. bigint operator+(const bigint &b) const //bigint加法
  125. {
  126. bigint ans;
  127. memset(ans.element, 0, sizeof(ans.element));
  128. ans.len = len;
  129. for (int i = 0; i < len; i++)
  130. {
  131. ans.element[i] += element[i] + b.element[i]; //加
  132. if (ans.element[i] >= BASE) //如果多了就借位
  133. {
  134. ans.element[i + 1] += ans.element[i] / BASE;
  135. ans.element[i] %= BASE;
  136. }
  137. }
  138. ans.len++;
  139. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  140. {
  141. ans.len--;
  142. }
  143. return ans;
  144. }
  145. bigint operator-(const bigint &b) const //bigint减法
  146. {
  147. bigint ans;
  148. memset(ans.element, 0, sizeof(ans.element));
  149. ans.len = len;
  150. for (int i = 0; i < len; i++)
  151. {
  152. ans.element[i] += element[i] - b.element[i]; //减
  153. if (ans.element[i] < 0) //如果多了就借位
  154. {
  155. ans.element[i] += BASE;
  156. ans.element[i + 1]--;
  157. }
  158. }
  159. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  160. {
  161. ans.len--;
  162. }
  163. return ans;
  164. }
  165. bigint operator*(const bigint &b) const //bigint乘法
  166. {
  167. bigint ans;
  168. memset(ans.element, 0, sizeof(ans.element));
  169. ans.len = 2 * len;
  170. for (int i = 0; i < len; i++)
  171. {
  172. for (int j = 0; j < b.len; j++)
  173. {
  174. ans.element[i + j] += element[i] * b.element[j]; //乘
  175. if (ans.element[i + j] >= BASE) //如果多了就借位
  176. {
  177. ans.element[i + j + 1] += ans.element[i + j] / BASE;
  178. int cur = i + j + 1;
  179. while (ans.element[cur] >= BASE)
  180. {
  181. ans.element[cur + 1] += ans.element[cur] / BASE;
  182. ans.element[cur] %= BASE;
  183. cur++;
  184. }
  185. ans.element[i + j] %= BASE;
  186. }
  187. }
  188. }
  189. ans.len++;
  190. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  191. {
  192. ans.len--;
  193. }
  194. return ans;
  195. }
  196. bigint operator/(const ll &b) const //bigint除法 element len/b(先撸个半成品，这玩意儿太鬼畜了)
  197. {
  198. bigint ans;
  199. memset(ans.element, 0, sizeof(ans.element));
  200. ans.len = len;
  201. ans.element[len - 1] = (element[len - 1]) / b;
  202. ll lef = element[len - 1] % b;
  203. for (int i = len - 2; i >= 0; i--)
  204. {
  205. ans.element[i] = (element[i] + lef * BASE) / b;
  206. lef = (element[i] + lef * BASE) % b;
  207. }
  208. ans.len++;
  209. while (ans.element[ans.len - 1] == 0 && ans.len > 0) //清除空白高位
  210. {
  211. ans.len--;
  212. }
  213. return ans;
  214. }
  215. void bigint_init()
  216. {
  217. memset(element, 0, sizeof(element));
  218. len = 0;
  219. }
  220. bool bigint_read()
  221. {
  222. memset(in, 0, sizeof(in));
  223. scanf("%s", in);
  224. // if (!(strlen(in) == 1 && in[0] == '0'))
  225. // return false;
  226. *this = in;
  227. return true;
  228. }
  229. void bigint_print()
  230. {
  231. if (len == 0)
  232. printf("0");
  233. else
  234. {
  235. printf("%lld", element[len - 1]);
  236. for (int i = len - 2; i >= 0; i--)
  237. {
  238. printf("%09lld", element[i]);
  239. }
  240. } //注意输出的时候除了第一位其他不够位数都用0补齐(避免遗漏前缀0)
  241. printf("\n");
  242. }
  243. };
  244. int main()
  245. {
  246. cout << "Please enter the target number: ";
  247. ll maxm;
  248. cin >> maxm;
  249. bigint a;
  250. a.bigint_init();
  251. a = 1;
  252. bigint b;
  253. b.bigint_init();
  254. b = 5;
  255. bigint c;
  256. c.bigint_init();
  258. bigint q;
  259. q.bigint_init();
  260. q = 2;
  261. bigint w;
  262. w.bigint_init();
  263. w = 4;
  264. for (ll i = 2; i <= maxm; i++)
  265. {
  266. if (i % 3 == 2)
  267. {
  268. c = b * q;
  269. c = c - a;
  270. c = c + w;
  271. }
  272. else if (i % 3 == 0)
  273. {
  274. a = c * q;
  275. a = a - b;
  276. a = a + w;
  277. }
  278. else
  279. {
  280. b = a * q;
  281. b = b - c;
  282. b = b + w;
  283. }
  284. }
  285. cout << "The answer is: ";
  286. if (maxm % 3 == 0)
  287. {
  288. a.bigint_print();
  289. }
  290. else if (maxm % 3 == 1)
  291. {
  292. b.bigint_print();
  293. }
  294. else
  295. {
  296. c.bigint_print();
  297. }
  298. }
/*
 * @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();
    }
}

《“离散数学——冯诺依曼邻居问题”》 有 1 条评论

  1. 匿名说道：
    2020年7月1日 上午11:19

    噜噜噜噜噜噜噜

    回复

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

你好 No.97615