很久很久以前，巨龙突然出现，带来了灾难带走公主又消失不见。王国十分危险，世间谁最勇敢，一位英雄出现…… 学习于该大佬博客 题意 那么你就是这位英雄，不过不同的是，你面对的是一群巨龙，虽然巨龙都不会攻击；你每次使用的剑一打就爆，虽然每打死一条巨龙的奖励是一把新的剑；巨龙不会因为生命值降为负数而死亡，虽然巨龙会憨憨地回血然后把自己奶死；最重要的是你完成游戏不会获得公主的爱，只会获得...

P4827 [国家集训队] Crash 的文明世界 题意 求出对于树上每个点 \(x\) 的 \(\sum_{u=1}^ndis(x,u)^k\)。所有边长为 1。 思路 根据斯特林反演： \[ m^n=\sum_{j=0}^n\begin{Bmatrix}n\\j\end{Bmatrix}C_m^jj! \] 可以得到： \[ \sum_{i=1}^n\sum_{j=0}...

P5042 丢失的题面 顺序：10 - 1 - 7 - 8 - 9 - 4 - 5 - 6 - 2 - 3 Point 10 读入，特判，输出。 读入的英文意思是让选手输出自己的程序本身，这个题的确存在，但是这题并没有 SPJ ，所以特判一下输出输出文件就好了。 C++ 的atoi函数可以让读入的字符串变成数字以完成其他点的任务。 Point 1 我和其他聚铑做这个点的过程...

P5110 块速递推 题意 多次询问，求数列 \[ a_i=\begin{cases}233a_{i-1}+666a_{i-2} & i>1\\ 0 & i=0\\ 1 & i=1\\ \end{cases} \] 的第 \(n\) 项在 \(\mod 1e9+7\) 意义下的值的异或和。 思路 首先这个数列是一个广义斐波那契数列。对于广义斐波...

P5147-数学-随机数生成器 （洛谷第一篇题解说这是高一数学题，新高二感觉到被吊打） 我们设work(x)的期望值为\(f_x\) 注意\(f_1\)是边界。不过对下列式子没有影响。原因参照必修的数列 那么\(\displaystyle f_n=1+\frac{1}{n}\sum_{i=1}^{n}f_i\) 移项得到\(\displaystyle f_n=\frac{n}{...

P5296 [北京省选集训2019]生成树计数 题意 求一个带权无向图所有生成树边权和的 \(k\) 次方的和。 思路 首先有一个结论：\(a^i\) 的 EGF 卷 \(b^i\) 的 EGF 等于 \((a+b)^i\) 的 EGF。即： \[ F(a)=\sum_{i=0}\frac{a^ix^i}{i!}\\ F(a+b)=F(a)*F(b) \] 证明如下： \[...

P5311 [Ynoi2011] 成都七中 题意 给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。 查询操作给定参数 \(l\ r\ x\)，需输出： 将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。 每次查询操作独立。 思路 考虑点分树的思想。假设我们已经建出点分树，对于每一个分治中心，我们应该...

P5350 序列 题意 维护一个序列，支持区间求和、赋值、加值、复制、交换、翻转操作，其中交换和复制操作保证两段区间长度相等且不交。答案对 \(1e9+7\) 取模。 思路 对于区间求和、赋值、加值、交换、翻转操作我们都可以很轻松地使用平衡树进行维护。所以现在的难点就在于复制操作：如何复制一段区间？ 如果我们暴力复制的话，每次我们不得不将被复制的子树扫一遍进行复制，这是肯定不行的...

P5471- K-D tree优化建图-弹跳 优化建图是一种思想。 题意 有\(n\)个城市分布在小鸟岛上，有\(m\)个弹弓分布在这些城市里。因为弹弓体积大，固定麻烦，所以每个弹弓只能把小鸟弹飞到一块固定的矩形范围内的城市，同时小鸟会在空中滞留\(t_i\)的时间。闪电黄的家在1号城市，追求速度的它想知道，若只使用弹弓出行，它从家到其他所有城市的最短时间花费是多少。 抱歉魔...

P6106 [Ynoi2010] Self Adjusting Top Tree 题意 给出平面直角坐标系上若干不与坐标轴平行的处于第一象限的互不相交的线段，多次询问平面中一个第一象限的矩形与这些线段相交部分的长度长度和与所有线段长度和的比值。给出的所有坐标 \(\in[1,10^6]\)。 思路 假设所有线段的斜率都是正的，考虑将询问差分成四个前缀矩形。我们只需要考虑统计若干斜...