计数DP

矩阵加速计数

对于一类线性递推计数问题，可能遇到 \(n\) 很大的情况，这个时候 \(O(n)\) 的 DP 都是不可通过的。这个时候就需要考虑写出转移矩阵，用矩阵乘法加速计数。这是一类重点问题，且可以出得有一定难度。
例题

P3702 [SDOI2017] 序列计数
考虑用总方案数减去一个质数都不选的方案，两个方案数都很好用矩阵转移。代码 。
众数计数

关于一个区间的绝对众数的相关计数问题，朴素的状态设计为 \(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 [CSP-S 2019] Emiya 家今天的饭
这一道题就是上述优化的一个模板应用。代码 。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

收藏一下   不知道什么时候能用到