AGC013E Placing Squares 发表于 2025-02-25 更新于 2025-02-26 分类于 算法竞赛 ， 题 ， AtCoder 阅读次数： 题意：给定一条长为 的线段，线段上有 个标记点。 将线段切分为若干段，每一段的长度都要是整数，且不能切在标记点上。 设切为 段，且第 段的长度为 ，则这种切分的权值为 。 求所有合法切分的权值和。答案对 取模。 ，，时限 。 考虑 。 记 为切分 的所有合法方案的权值。 当 为标记点， 。 否则，则有转移 于是，维护 则有 当 为标记点，有 上述转移不难用矩阵描述，使用矩阵快速幂，即可做到 。