下次数数题做不出来的时候看看这个。

dead_X · 2023-11-13 15:16:54 · 个人记录

算贡献

贡献是否可以写成若干元素的和？

如果可以，将题目弱化为“对于求和的每一部分，分别算出这部分被计入答案的次数”，将数 sum 变成数 cnt。

符合要求的序列/树是否可以分段构造？是否存在状态数较少的子结构？

如果感觉有但是找不到：将序列逆序，将矩阵转置，将排列求逆，将树改为自上向下构造。

是否有你认为“状态很少”但难以简单地遍历状态的结构？如果有，尝试使用搜索检查状态数量，并进行适当的剪枝。

例子：[NOI2022] 移除石子，[ZJOI2019] 麻将。

是否存在 DP 的某一维非常大（10^9 或 10^{18}）但做法用到关于这一维的信息较简单？如果有，尝试构造转移矩阵。

一个合法的组合对象是否需要同时满足一些互相相关的条件？其反面的条件是否更简洁？

对于“连通”的条件可以枚举其包含某个点的极大连通块。

对于一些可以支持在线判断的条件可以枚举第一个不合法的位置。

一些形如“恰好”的限制是否会将问题的复杂度上升到不可接受的范围？

弱化掉一些形如“不同”或者“相同”的限制后，问题是否会变得可做？

如果可以，尝试在保持这个做法可以生效的同时增加一些钦定的性质，再套二项式反演。

例：[ARC121E] Directed Tree。

对 [d|\gcd(x,y)] 计数是否比 [\gcd(x,y)=d] 计数更简单？

将答案乘上 \mu(x) 之后是否仍然使用筛法？

是否存在 DP 的某一维非常大（10^9 或 10^{18}）但做法用到关于这一维的信息较简单？

问题关于某一个参数的答案是否可以写成一个多项式的形式？

例：[省选联考 2022] 填树。

这块 NOI(P) 应该不能考。

括号：折线，树。

环：断环为链。

序列：差分，前缀和。

组合数：把 n 个球分成 m 段。

组合数：从 (0,0) 向右向上走到 (n,m)。

分数：在 n 个球内随机选 m 个。

如果这些都不管用剩下的估计也就只有外星人会做了，建议直接跳题。

问题是否可以递推求解？是否可以在代码长度内储存所有信息？

是否可以在合理的时间内打完表？能否承担考场机子爆炸带来的损失？