描述
分析
- 如果用 f[i] 表示 i 时 Concatenate(1 .. i) Mod M 的值, 如果 i 是个 k 位数, 则 f[i+1] = f[i] * (10^k) + i+1, (i != 10^k-1)
- 所以可以建立一个按 i 的位数分段的动态规划解法 -> f[n]
- n ≤ 10^18, 所以要用矩阵乘法优化
- 然后就是矩阵的选取了, 我首先考虑的 2×2 的矩阵能不能解决, 发现不能于是看了一下 HZWER 开的数组大小是4, 所以应该是 3×3 的矩阵了.
- 之所以 2×2 的友矩阵不能解决是因为 如果把矩阵 {f[i], i} 设为求解的矩阵, 那么无论乘哪个 2×2
的友矩阵都不能在转移到 f[i+1] 时使第二列的 i 也加1
- 那么用 3×3 的友矩阵, 求解的矩阵
{f[i], i, x}. 这个 i 要想每次加1, 只能依靠这个 x 乘上友矩阵的 a[2][2] (从0开始的下标) 所代表的数. 所以把x和a[2][2]都设置成1就可以使i每次加1了.
- 关于矩阵的其他元素.
- 我的思路是第一次求 f[0], 乘10次之后得到 f[9], 然后进入下一层. 根据转移的方程可以得到友矩阵是 {{k,
0,
0},
{1,
1,
0},
{0,
1,
1}},
其中k是方程中的 10^k. 这样每次乘完之后得到的是 {f[i+1], i+2, 1}. 然后我看HZWER的思路中的友矩阵是
{{k,
0,
0},
{1,
1,
0},
{1,
1,
1}},
这样每次得到的是 {f[i+1], i+1, 1}.
- 其实两种思路都可以得到最终解.
- 当转移到下一阶段时,
k要×10, 之后友矩阵自乘的次数是 k-k/10. 因为举个例子从 f[10^m-1]转移到f[10^(m+1)-1]实际上转移了10^m-10^(m-1)次.
- 但是按照我的思路,
在k=10的时候 10-10/10 = 9, 但实际上要转移10次, 所以程序开始要先单独处理k=10, 然后循环 k = 100 to ..
- 当 k > n 之后还需要继续转移的次数是 n-k/10+1 次.
- long long 和 快速乘 都是需要的.
代码
BZOJ-2326-数学作业-HNOI2011-矩阵乘法
原文：http://blog.csdn.net/qq_21110267/article/details/44809755
