冷滟泽的个人博客

2021-06-28 lengyanze 阅读(147) 评论(1)

NOI2016 循环之美 题解 1. 题意 求在 K 进制下，表示为 \dfrac{x}{y}(x\leq N,y\leq M) 的不相等纯循环小数个数。 N,M\leq 10^9,K\leq 2000。 2. 模型...

2020-07-23 lengyanze 阅读(90) 评论(0)

参考 2018 年高睿泉的集训队论文《浅谈保序回归问题》。 保序回归问题 定义 保序回归问题是指，对于一个正整数 p，给定一个偏序关系（有向无环图），图中每个点 i 有权值 (w_i,y_i)，你要给每个点赋上另一个...

2020-07-07 lengyanze 阅读(57) 评论(0)

P4002 [清华集训2017]生成树计数 Tag：Prufer 序列 / 组合计数 / 多项式 我们使用 Prufer 序列来表示一棵树，在原图中的同一连通块中的点标为一种颜色。设第 i 个连通块的大小为 a_i，...

2020-06-03 lengyanze 阅读(49) 评论(0)

首先转化题意，对于确定的两棵树，设它们的边集分别为 E_1,E_2，则 E_1\cap E_2 形成了一棵森林，当前方案对答案的贡献为 y 的连通块数次方，即 y^{n-|E_1\cap E_2|}。下面对本题的三问...

2020-05-26 lengyanze 阅读(50) 评论(0)

设 a_i 表示原数组，b_i 表示所有长度为 i 的区间的权值和。首先我们对于一对 (i,j) 求出 a_i 对 b_j 的贡献（点对点）。发现这实际上就是求有多少个长度为 j 的区间覆盖了位置 i，讨论左端点的范...