Open ManuShi98 opened 3 years ago
https://manushi98.github.io/2018/01/21/HDU%20-%206185%20Covering/
思路类似插头dp的题，但数据范围到了10^18次。我们发现他的宽度只有4，若我们令a[n]为方案数，b[n]为不可分割的矩阵数，通过打表我们能发现a[1]=b[1]=1，b[2]=4，且n>=3时有：当n为奇数时：b[n]=2当n为偶数时：b[n]=3我的理解是更多分割的方案在之前已经有过计算，所以只有把原有的矩阵拉长的方案没有计算过，我们使用递推式计算就是要使用这一部分。最后计算可得a[n
https://manushi98.github.io/2018/01/21/HDU%20-%206185%20Covering/
思路类似插头dp的题，但数据范围到了10^18次。我们发现他的宽度只有4，若我们令a[n]为方案数，b[n]为不可分割的矩阵数，通过打表我们能发现a[1]=b[1]=1，b[2]=4，且n>=3时有：当n为奇数时：b[n]=2当n为偶数时：b[n]=3我的理解是更多分割的方案在之前已经有过计算，所以只有把原有的矩阵拉长的方案没有计算过，我们使用递推式计算就是要使用这一部分。最后计算可得a[n