P4494 [HAOI2018]反色游戏 题意 给你一个无向图，图上每个点是黑色或者白色。你可以将一条边的两个端点颜色取反。问你有多少种方法每个边至多取反一次使得图上全变成白色的点。 思路 若任意一个连通块黑色点的个数为奇数那么无解。 先考虑树的情况。发现如果是树，并且黑点个数为偶数，有且仅有一种方式达到目标。然后发现，对于一个无向图，它的任意一个生成树若有解，那么其他非树边无论是...

P4293 [WC2010]能量场 题意 给你 \(n\) 个粒子，每个粒子有两个权值 \(m_i,c_i\) 每个相邻有序对 \((a,b)\) 会产生 \(m_am_b(c_a-c_b)\) 的贡献。现让你处理两个问题： 找出一个有序对使贡献最大。 找出一个序列成环后贡献和最大。 思路 我们将贡献转化一下： \[ m_am_b(c_a-c_b)=m_ac_am...

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

P4334 [COI2007] Policija 题意 一个无重边的无向图，每次询问删掉一条边或删掉一个点后两个点是否联通。 思路 连通性问题，我们可以考虑使用广义圆方树解决。 对于删掉一个点的情况： 我们先跑 tarjan 建出圆方树。如何判断两点在删去一个点后在树上的连通性？当且仅当被删去的点在两点间的路径上。根据圆方树的性质，如果被删点在一个点双连通分量中，它是符...

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\) 意义下的值的异或和。 思路 首先这个数列是一个广义斐波那契数列。对于广义斐波...

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) \] 证明如下： \[...

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}{...

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