题解/算法 {J - Iris‘ Food}

题解/算法 {J - Iris’ Food}

@LINK: https://codeforces.com/gym/105184;

比如最终答案是: 1 0...0 1...1 2...2 3...3, 则其值 为1*10^? + (1...1)*10^? + (2...2)*10^? ...;
因此, 如何求2....2这个值(长度为1e9), 使用矩阵优化DP, DP定义为: DP[i]: 长度为i的2...2的大小, DP递推为DP[i] = DP[i-1]*10 + 2, 他可以写成DP[i-1] * 10 + 2 * 1, 即DP矩阵为[DP[i-1], 2] (也可以是[DP[i], 1]) 然后求他们的参数矩阵;