施工中 A. 简单计数 普通做法 考虑矩阵二项式： 则有： 降智严重的做法 构造矩阵 ，那么对于矩阵 ，有 就是答案 可以发现它是一个循环矩阵，因此可以只用第一行来表示，设 ，那么它在模 意义下的 次幂的 即为答案 进一步可以发现， 是相同的，因为它们的图论意义下是完全图上的本质相同点 于是可以只用 来表示 那么循环卷积一次相当于： 对于 ，有： 对于 ，有： 整理可得： 那么只需要维护 即可，因为 设 ，则： 其中 ，设 ，由于 ，可以发现它是一个二阶常系数齐次递推 设 ，则： 由于 ，所以 ，因此有两个不同的根 于是有： 由于 ，可以得到： 因此： 因此：...

数据结构经典问题…… 也可以在这里提交：https://loj.ac/problem/6145 如果你做过 https://ac.nowcoder.com/acm/contest/393/F，那么你一定会对这个题感觉很水的……（在线做法） 一个方便做的大前提：由于边权非负，因此重复经过某条边是不会计算到最后的答案中的 在线做法的话，就动态点分治，对于每一层分治中心用线段树维护最小值即可 离线做法就比较鬼畜且麻烦了

emm比赛的时候脑抽了……被题解做法吊打…… 不妨考虑暴力怎么做： 表示前 i 个元素，删除了 j 个，第一个集合减去第二个集合等于 k 是否可行，转移就 bitset 一下把第三维压了即可 题解就比较高明了，直接把第二维作为答案记录到了状态中……就是 表示前 i 个元素，第一个集合减去第二个集合等于 j，此时最少的删除元素个数 感觉特别像今天晚上的 2050 那个比赛的 1006 题

https://czyhe.me/blog/algorithm/nowcoder-560-B/nowcoder-560-B/ [题目链接](https://ac.nowcoder.com/acm/contest/560/B) # 题目大意 定义一个序列的权值为所有元素的乘积 求所有长度为 k 的正整数序列中，满足所有元素的和小于等于 S，把它们的权值加起来输出 答案模素数 p，其中 # 题解 设 表示长度为 i，和为 j 的答案，则： 生成函数为： 由于要求前缀和，再卷上 ，也就是： 因为： 所以： 卢卡斯定理一下就好了

欢迎来我的博客玩：czyhe.me 欢迎来洛谷点赞：https://www.luogu.org/blog/KingSann/heoi2019-you-ji day -??? noip 考挂了，校队垫底，上一名虐我 50pts+…… 我就是个 410pts 的菜鸡…… day -?? 到冬天了，神仙们都去 pkuwc/thuwc/noiwc 了，作为 noip 的垫底三连选手之一，我和 SGColin 以及 lokiii 去了 ccpc-wannafly camp 每天的体验：能过题就不错了，还没部分分就自闭得了 达成成就：猜结论过了一个题 学习了一些很有趣的知识： 笛卡尔树 解微...

感人肺腑，加了硬核优化和一大堆inline才行…… 出题人难道写的是 $O(n)$ 的算法吗……

A. 字符串 题目分析 显然，我们要求的答案是。 那么成为答案的那个区间一定是连续的一段A,B两串相等的子串。否则，若我们选择的不是连续的A,B相等的子串，那么我们可以让选择现在选择区间左右两边相等段更长的那个那段，使答案单调不劣。 B. SHTMYCBDFTT 题目大意 给定一个序列，求一个子串，使得数字的异或和加上所有的数字最大 题目分析 根据异或的定义，可以得到：，原因是： 设当前集合 的和为 ，异或和为 ，有一个元素 没有添加 因为 ，所以还可以添加元素 进入集合，所以 应该是全集 C. 出题的诀窍 题目大意 给定一个二维数组 ，求： 其中 表示这个序列中所有不同的数的和，相...