总结

腊月初七。今天是 csy 讲计数问题。

H. Horrible Cycles

一种经典的 dp 思路。（经典吗？）就是填坑之类的那种。

hitachi2020_f Preserve Diameter

就是一个树，要满足加几条边后的简单图的直径不变，并且连上任意一条没有连上的边后直径都会变小。容易发现只有一条直径。以一个端点建立它的 bfs 树，容易发现同层之间都有边，相邻层之间也全有边。也就是一个和两个数组对应。然后深度最深的点只有一个。发现由于直径必过树的中心，所以在树的中心 dp，深度还是刚才的深度，然后树上 dp 就行。两个点之间转移就是。因为两个点上深度之差不会超过。链是偶数的话把两个中心分开 dp，然后合并就行。

CF1264D2 Beautiful Bracket Sequence (hard version)

题意大概就是给你一个括号序列，有一些位置未知。然后对于一个括号序列的权值就是某个子序列最深的括号层数。容易发现就是一个位置割开两边左括号和右括号数量取。容易发现左右相等的时候一定是最大的。因为往右移动一格要么左括号多一个要么右括号少一个，所以容易发现这个。所以枚举选择的位置，另当前这个分割左边有个左括号和个问号，右边有个右括号和个问号，得到式子：

这里用了范德蒙德卷积，很有趣吧。

P.S. 话说怎么加了一个范德蒙德卷积怎么就变黑了？好离谱。

CF1450H2 Multithreading (Hard Version)

这道题暑假刘一平讲过。容易发现就是合并相邻的吧，一定是位置一奇一偶，最后是交错的。所以发现对于假设一个颜色白色吧，假设奇数位置有个，偶数位置有个，那么交点最少就是。

然后把式子列出来，然后推一下就行。有点复杂。

Interval-Free Permutations

给定一个模数和，请您输出长度为同时不包含连续子段的排列方案总数。

用到一点析合树的知识。先简单在 OI-WIKI 上面看一下：析合树 。

构造似乎用不到，就先没看了。

就是一个比较简单的容斥就是了。复杂度。

后记

锐评今天早上的语文考试作文，据说是议论语文书的好处。（某同学说是赞美语文书，还有说赞美 wrm 的，逐渐离谱）。挺好玩的，但看起来考试的同学并不这么认为。

最近有点烦躁啊，好想清净一点。·。突然在我的字典上面发现了一只蚊子的尸体，旁边看起来还有个什么虫的尸体。不知道什么时候上去的。或许这只蚊子只是想看看字典，学学人话吧，哈哈，希望它下辈子是个人。

今天 junjun 看到一只蜘蛛，蜘蛛在窗帘上爬。但是 junjun 极度恐慌，我和 pigeon 去看，我并不是很想就这么打死一只蜘蛛，又没招谁惹谁。最后 pigeon 光荣地帮助 junjun 打死了蜘蛛，哎，可怜的蜘蛛，希望 pigeon 不要太难过。