51Nod 部分题目 の 口胡&一句话题解

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod-One-Sentence.html

51Nod1404  先列出式子,然后搞成一个组合数。然后 lucas 定理一下,转化成比模数小的组合数。模数很大,打表预处理阶乘即可。

51Nod1026  枚举底数,然后按照指数值域分类,最后容斥一下就好了。

51Nod1033  状压dp一下,矩阵快速幂优化转移。

51Nod1261  考虑每一个上升数都是大于 $9$ 个形如 $11cdots 11$ 的数之和,我们将所有形如 $11cdots 11$ 按照对于 $K$ 取模的结果分类,然后 dp 一下即可。

51Nod1291  单调栈 + 对于每一行二重差分就可以了。

51Nod1250  第一问 dp ,第二问可以考虑根据最终的序列,形成多个环,问题转化成了分成多个环计数,直接上第一类斯特林数即可。

51Nod1231  证明竞赛图的一个重要性质,然后 DP 。

51Nod1626  显然是个状压 DP + 矩阵快速幂优化。重点在于 对状态的去重 和 对无效状态的删除 。

51Nod1375  莫比乌斯反演

51Nod1115  考虑把连续的一坨正数以及一坨负数以及负数压缩成一个数,对于可以选择的段数<正数段数的情况,考虑贪心的选择 删除一段正数 或者 选择一段负数以连接它两端的正数。这个东西用个 set 即可;维护相邻信息直接链表。这个套路好像哪里见过……

51Nod1038  模质数意义下的高次剩余模板题。

51Nod1039  模质数意义下的3次剩余模板题,但是卡常数,好像有个跑的很快的随机化做法。

UPD 这篇文章貌似咕掉了……

原文地址:https://www.cnblogs.com/zhouzhendong/p/51Nod-One-Sentence.html