计数DP
矩阵加速计数对于一类线性递推计数问题，可能遇到 \(n\) 很大的情况，这个时候 \(O(n)\) 的 DP 都是不可通过的。这个时候就需要考虑写出转移矩阵，用矩阵乘法加速计数。这是一类重点问题，且可以出得有一定难度。
例题
P3702 序列计数
考虑用总方案数减去一个质数都不选的方案，两个方案数都很好用矩阵转移。代码 。
众数计数
关于一个区间的绝对众数的相关计数问题，朴素的状态设计为 \(f_{i,j,k}\) ，表示要选为众数的数选了 \(j\) 个，非众数的数选了 \(k\) 个的方案数。但是考虑对绝对众数的要求是出现次数 > \(\lfloor \frac{n}{2} \rfloor\) ，因此我们只关心 \(j-k\) 的值，于是可以用 \(f_{i,j}\) 表示原状态中 \(j-k\) 的值，从而把 DP 从 \(O(n^3)\) 优化到了 \(O(n^2)\) 。
例题
P5664 Emiya 家今天的饭
这一道题就是上述优化的一个模板应用。代码 。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 收藏一下 不知道什么时候能用到 感谢分享，学习下。 过来提前占个楼 感谢分享，学习下。 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 收藏一下 不知道什么时候能用到 收藏一下 不知道什么时候能用到 很好很强大我过来先占个楼 待编辑 感谢分享，下载保存了，貌似很强大 前排留名，哈哈哈 不错，里面软件多更新就更好了 这个有用。 谢谢楼主提供！ 这个有用。 yyds。多谢分享 谢谢分享，辛苦了 懂技术并乐意极积无私分享的人越来越少。珍惜 不错，里面软件多更新就更好了 东西不错很实用谢谢分享
页:
[1]
2