本周小结

本周并未学习什么算法，而是再深入了解了根号分治，复习了一点数据结构。
开学第二周，制定了读书计划与刷题计划。

根号分治2

按照老师的话，“小的东西种类不多，大的东西倍数不多”。根号分治不仅可以用来解决一些数据结构题，还可以用于复杂度的分析（空间与时间都可以）。比如熟知的“数论分块”的时间复杂度便是如此。
也有一些非经典的数据结构题可以使用根号分治，根号划分的内容不再是询问，而是一种“二级数据”。
一道题目：自然数拆分

传统解法

看成完全背包，解题。
另一种思路：定义状态\(f(i,j)\)：将\(i\)分成\(j\)个数的方案数。
此时的决策十分奇怪，有两种决策，为：
①加入一个\(1\)，即从\(f(i-1,j-1)\)转移
②将已有的所有数\(+1\)，即从\(f(i-j,j)\)转移
\(j\)应该放于外层循环，可惜时间复杂度还是\(O(n^2)\)

小东西

直接计算\(\leq L\)的完全背包，记为\(g[]\)

大东西

只需要定义状态\(H(i,j)\)：将\(i\)分成\(j\)个数，这\(j\)个数都大于等于\(L+1\)的方案数。
\(h[i]\)为\(i\)分成若干个不小于\(L+1\)的数的方案数。

答案

\(ans=sum_{i=0}^n{g[i]*h[n-i]}%p\)

Floyd判圈算法

没啥好记录的，很简单。

2021-09-12算法周记——根号分治2

原文：https://www.cnblogs.com/wyc06/p/15259815.html