作者： | 来源：互联网 | 2023-06-23 21:04
解题方法：难点在于模型转化$a_{i}^2$可以被转化为在$a_i$个格子里放2个不同的小球（两个小球可以放在同一个格子里）的总方案数然后我们设$dp[i][012]$表示在i所属
解题方法：
难点在于模型转化
$a_{i}^2$可以被转化为在$a_i$个格子里放2个不同的小球（两个小球可以放在同一个格子里）的总方案数
然后我们设$dp[i][0/1/2]$表示在i所属的区间内放置0/1/2个小球的方案数，转移比较显然
然后我们发现这个转移是可以用矩阵快速幂处理的
由于m的值较小，对于M个标记格子的转移，只需要枚举转移即可
时间复杂度：$O(mlog(n/m)*27)$
京公网安备 11010802041100号