文章

传送门 感觉自己是傻子系列 为了锻炼自己的推式子能力就去网上搜 $stirling$数随机到了这一题 然后就开始愉快的推啦！ 首先很容易发现每个数 $w_i$是等价的，我们只需要考虑一个数的贡献 由题意，我们就枚举这个数在大小为 $j$的集合里，那么有 $$\sum_{j=1}^n jC_{n-1} 阅读更多…

喵 题意 求 $$\sum_{i=1}^n C_n^i i^k$$ 题解 第二类 $stirling$数模板题没错了 根据套路化简 $$\sum_{i=1}^n C_n^i \sum_{j=1}^k A_i^jS_k^j$$ 交换枚举顺序 $$\sum_{j=1}^k S_k^j j!\sum_{i 阅读更多…

看题目可以去这个 blog 看看 题解 首先简化一下题目 它要求的就是 $$\sum_{S \in V} |f(S)|^m$$ 其中 $S$是一个点集，$f(S)$指的是点集所形成的边集，形式化来讲就是 $f(S)=\{(u,v)|u\in S \&\& v\in S\&am 阅读更多…

传送门 自己姿势太低乱搞的时候只会构造，不会求最小 题解 首先显然只要有黑色格子就有方案。 然后我在搞的时候尝试证明一些类似充分必要的东西转换条件但是没想到= = 果然是太垃圾了只能去看题解 然后就会发现跟什么充分必要没啥关系 首先我们会发现，如果某一列有一个白色格子，它一定会被覆盖至少一次 当且仅 阅读更多…

这道题一共有两问，第一问瞎搞 $\texttt{DP}$ ，第二问如果直接 $\texttt{DP}$ 的话复杂度是 $O(n^4)$ 的过不去，这个时候需要用到决策单调性优化复杂度就可以降低至 $O(n^3)$ ，这样就过了。我们先来讨论一下第一问的做法。 时间的范围太大了，我们需要离散化一下。离 阅读更多…

题目 据说是套路题= = 那我们就放三种方法～ 题解 第一种是我 $yy$的 考虑一条合法的最短路，它的最后一条边一定指向一个关键点，那么我们可以记录每个点到最近关键点 $(u_1,dis_1)$和第二近关键点 $(u_2,dis_2)$，这里只需要保证 $u_1\ne u_2 \&\&am 阅读更多…

传送门 题外话 这道题题面有毒我笑死了 $qwq$ 不过题面第一句话读了有点伤感 $QAQ$ 题解 这是一道加深对后缀自动机理解的好题呀 $qwq$ 首先简化一下题意，我们就是要找一对 $(x,y)\in [l,r]\;x\ne y$，使得字符串 $S_{1,l}$和 $S_{1,r}$的最长公共后 阅读更多…

圆方树。 我们建立圆方树之后枚举每个起点和终点。 然后设方点的权值为点双的个数，圆点的权值是-1。 之后可以得到答案就是两点之间的点权和。 之后不难发现对于一个点的贡献可以用一遍 $\text{dfs}$得到, 这道题就做完了。 // luogu-judger-enable-o2 #include 阅读更多…

单位根反演不会啊怎么搞 $FFT$ 吧，还是了解了单位根反演后才可以搞的好吧…… 居然有人吐槽我说我学了 $FFT$ 但是不会运用？！，嘤嘤嘤打击有些大…… 实际上所谓的单位根反演就是这个东西： $$\frac{1}{n}\sum_{i=0}^{n-1 阅读更多…

$myy$ 出的神题…… 貌似正解并不难但是没有人切…… $30$ 分可以用 $DP$ ，设 $f[i][j]$ 表示 $i$ 到 $j$ 是否有一条满足条件的路径。对于有一条满足条件的路径的 $i,j$ ，我们枚举连接 $i$ 的点和连接 $j$ 的 阅读更多…