P6295 有标号 DAG 计数 题意 求 \(n\) 个点有标号弱联通 DAG 数量。 推导 设 \(f_i\) 表示 \(i\) 个点有标号 DAG 数量（不保证弱联通），有： \[ f(i)=\sum_{j=1}^i\binom ij(-1)^{j-1}f(i-j)2^{j(i-j)} \] 意义为选至少 \(j\) 个度数为零的点，向剩下的 \(i-j\) 个点随...

P5658 括号树 NOIp2019 我是永远不会忘记我那天在考场上傻瞪着题啥都不会的心理阴影的…… 于是今天我克服心理阴影来写这道题。 树形结构 因为这是一个树，所有优秀的性质这个题都有。并且题目仅仅是问从1开始到所有点的答案，所以我们就可以依靠树的性质来做。 首先，对于一个节点，我们给它记录几个值： \(lst_i\)表示i的贡献（只是i的贡献，并不包括从根节点到i路径...

P5468 [NOI2019] 回家路线 斜率优化入门（指我写的东西而不是这道题） 题意 \(n\) 个节点，有 \(m\) 趟列车，车 \(i\) 从 \(p_i\) 时刻至 \(q_i\) 时刻从 \(x_i\) 地到 \(y_i\) 地。猫猫需要只坐列车从 \(1\) 节点到达 \(n\) 节点。 设猫猫在一个地方等待的时间为 \(t\)，那么代价为 \(At^2+Bt+C\)...

P5591 小猪佩奇学数学 知识点 二项式定理 \[ (x+1)^n=\sum_{i=0}^n\binom nix^i \] 单位根反演 \[ [n\mid k]=\frac 1n\sum_{i=0}^{n-1}\omega_n^{ik} \] 证明： \[ [n\mid k]=\begin{cases}\frac 1n\sum_{i=0}^{n-1}\omega_n^...

P6753 [BalticOI 2013 Day1] Ball Machine 题意 给你一个树，每次从根节点放一个求，如果其子节点有空这个球会向下滚，若有多个节点为空则找儿子中以子树内编号的最小值为优先级从小到大找第一个为空的位置滚。 有两种操作，第一种插入若干个球，输出最后一个球到的节点编号；第二种删除一个位置，此时若有可以向下滚的球那么这个球就会滚，输出有多少个球滚了。 保证...

P6845 [CEOI2019] Dynamic Diameter 题意 一颗带权树，每次更改一条边的权，每次修改后求出最大直径。强制在线。 思路 \(O(n\log^2n)\) 的暴力做法。 根据经典结论，对于两个点集的树上最大直径（权值非负），并集点集的树上最大直径的端点一定是原四个端点中的两个。 那么我们就可以用线段树维护点集，合并时 \(O(\log n)\) 查询两点...

P7003 [NEERC2013]Hack Protection 题意 给定一个序列 \(a\) ，求有多少个区间满足区间内的数的异或和等于与的和的值。 思路 首先我们求一个异或前缀和 \(s\)，对于每一个区间 \([l,r]\) ，它的贡献为区间内按位与的和等于 \(s_r \bigoplus s_{l-1}\) 的段的个数。 设 \(x\) 为某个区间的按位与的和，...

P6982 [NEERC2015]Jump 题意 给你一个未知的 01 串，每次可以输出询问一个 01 串，如果该串中正确的个数刚好等于 \(n\) 或者 \(n/2\) ，将会返回相应的答案，否则会返回 0 。求出这个串。（询问次数不大于 \(n+500\)，\(n\leq 1000\)） 思路 先无视询问次数，我们来想一下确定性算法怎么做。 第一步，我们来试着找出 \(...

P7324 [WC2021] 表达式求值 闲话 WC2021 我只得了 20 分，三道题总共 20 分。我是下场了突然后知后觉这件事的，主要原因是我开了 C++11，然后 T1 T2 都没分了。在洛谷上测本来能拿银牌的。T1 的乱搞能拿 48，还挺高的。 幸亏咱们陕西省选不看冬令营成绩。幸亏是在省选前犯的这个错误。告诫后人和自己，写题前一定要看编译选项，否则只能后悔莫及。 T2 ...

P7362 [eJOI 2020 Day2] XOR Sort 题意 给你一个长度为 \(n\) 的序列，每次操作可以将一个数异或上相邻的一个数，求将序列改为严格单调递增序列或严格单调不降序列的操作次数的操作序列。 注意，改为严格单调递增序列的数据 \(n\leq 200\) 且每个数不相同，改为严格单调不降序列的数据 \(n\leq 1000\)。 不要求操作次数最小，次数需...