2022.9.17
组合数技巧
对于 \(\bmod 2\) 的组合数，进行卢卡斯后可得出结论： \(C_n^m=[n\textsf{&}m=m]\)
2022.9.24
可后悔贪心
A 城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出 \(n\) 个种树的位置，顺时针编号 \(1\) 到 \(n\)。并且每个位置都有一个美观度 \(A_i\)，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（\(i\) 号位置和 \(i+1\) 号位置叫相邻位置。值得注意的是 \(1\) 号和 \(n\) 号也算相邻位置！）。
最终市政府给园林部门提供了 \(m\) 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将 \(m\) 棵树苗全部种上，给出无解信息。
用优先队列，贪心地选择最大点 \(p\)，将其两侧的点 \(l_p,r_p\) 直接删除，并将原来的点赋值为 \(a_{l_p}+a_{r_p}-a_p\)，重新加入队列。这样如果 \(p\) 再次回到队头，就说明不选这个而选择旁边两个点更优，达到了贪心的反悔。
由于有删点操作，\(l\) 和 \(r\) 需要动态维护，而且反悔也会是嵌套的。
珂朵莉树
小 C 得到了一棵树。
这棵树有 \(n\) 个顶点，编号为 \(1\sim n\) ，这些顶点之间通过 \(n-1\) 条边相连。每个顶点染有一种颜色，初始时所有顶点都为 \(0\) 号颜色。现在小C想要进行 \(m\) 次操作。对于每次操作，小 C 先统计出 \(u_i\) 到 \(v_i\) 的路径上颜色编号为 \(c_i\) 的顶点个数，接着将 \(u_i\) 到 \(v_i\) 的路径上的顶点都染成 \(c_i\) 号颜色。
现在小 C 希望你可以帮他求出每次操作的统计结果。
先树链剖分转化成区间问题。
区间赋值是个很方便的性质，可以把值相同的区间合并，变成单个节点。
具体实现：
1 | //...// |
一道期望+换根 dp
（CF123E） >一个含有 \(n\) 个点的迷宫是一棵树（一个任意两点之间都恰好有一条路径的无向图）。每个点都有一定的概率成为这个迷宫的入口和出口。 > >从这个迷宫走出去的方法是从入口开始进行深度优先搜索。如果当前有多个移动方案，那么等概率的选择移动方案中的一个。（随机游走，但走完一个子树才会返回，往返均计入步数） >你的任务是统计一个人从这个迷宫的入口走到出口步数的数学期望值。
设立状态 \(f_i\) 表示从 \(i\) 走到其子树内的终点的期望步数。令 \(F_{i\to u}\) 为 \(i\) 到 \(u\) 的期望步数，\(P_u\) 为 \(u\) 是终点的概率，则有：
\[f_i=\sum_{u\in sub_i}(F_{i\to u})\cdot(P_u))\]
对于 \(i\) 的儿子 \(j\)，有转移：
\[f_i=\sum_{j\in son_i} f_j+\left(\sum_{u\in son_j}P_u\right)\cdot(siz_i-siz_j)\]
这个转移可以这样考虑：
对于终点在 \(j\) 子树内的那一部分概率（即 \(\left(\sum_{u\in son_j}P_u\right)\)），游走时可能会经过其他的子树，发现在其他子树内会经过的边数总共有 \((siz_i-siz_j-1)\) 条（算上连接 \(i\) 那条边），这时再加上 \(i-j\) 边，就变成了 \((siz_i-siz_j)\) 条，两者相乘，再加上子树内的期望步数...是这样的吗？
不，这个式子没有看起来那样单纯，事实上有一些系数互相抵消了。
考虑所有子节点的全排列，容易推出经过任意一个子树的概率都是 \(\dfrac{1}{2}\)，所以整体除以二。同时，由于往返边都要计算，所以整体还要再乘二。对于 \(i-j\) 边，虽然只经过一次，但经过的概率也为 \(1\)，不影响整体的抵消。
有了转移式子，接下来换根 dp 即可。
..实现的时候，发现现在居然还在犯少开 long long 的错误，防范之心不可无啊。
2022.10.15
扩展欧几里得
拖了这么久，总算把扩展欧几里得的式子完全推清楚了，是这样： \[ax+by=g,g=(a,b)\] \[ax+by=bx'+(a\bmod b)y'=g\] \[ax+by=bx'+(a-b\lfloor\frac{a}{b}\rfloor)y'=g\] \[a(x-y')+b(y-(x'-\lfloor\frac{a}{b}\rfloor))=0\] \[\therefore x=y',y=x'-\lfloor\frac{a}{b}\rfloor\] 处理后可得 \[ax+by=c\] 求最小正整数解： \[ax+by=a(x-\frac{b}{g})+b(y+\frac{a}{g})=c\] 先通过整除让 \(x\) 尽量接近 \(0\)，若仍负再加即可。
2022.10.18
三角序列
给定 \(n\) 组成对的数 \(a_i,b_i\)，每组数表示一个 \(a_i\) 行 \(b_i\) 列的如图所示的三角形
note-1.png 其中 \(b_i\) 为 \(0\) 时左边较低，为 \(1\) 时右边较低。
将每组数对应的三角按数的顺序从左到右拼接起来。
现给出 \(m\) 组询问 \(l_i,r_i,v_i\)，对每组询问求最低高度 \(h_i\) 使得 \(l_i\) 到 \(r_i\) 列之间的高度在 \(h_i\) 以内的
o的数量大于等于 \(v_i\)。
先把区间里的三角形掐头去尾特判，注意还有整个区间全在一个三角形里的情况。然后在剩下的三角形中对 \(h\) 进行二分，把三角形按照是否比 \(h\) 高分两类，低类可以通过可持久化线段树维持一定边长的总面积，而高类的面积可以发现是一个矩形（边长乘 \(h\)）减去一个固定的三角形（\(\dfrac{h^2-h}{2}\)），通过统计区间内低类总长、低类个数，可反推高类的面积和。
Little Elephant and Colored Coins
一头利沃夫动物园里的小象非常喜欢硬币，但是最重要的是他喜欢彩色的硬币。
他有N种类型的硬币，编号从 \(1\) 到 \(N\)，第 \(i\) 种硬币价值 \(V_i\) 美元，颜色是 \(Ci\)，对于每种硬币，他都有无限个。
这头小象想用这些硬币恰好组成 \(S\)美元。
组成这 \(S\) 美元的硬币最多能有多少中颜色？
如果不可能，输出 \(-1\)。
当然，这头小象有多个询问。
还得给个范围：
\(1\leq N\leq30\)
\(1\leq V_i\leq2\times10^5\)
\(1\leq C_i\leq10^9\)
\(1\leq Q\leq2\times10^5\)
\(1\leq S\leq10^{18}\)
发现 \(S\) 大的离谱，不能用朴素的背包之类来做。考虑 \(N=2\)，可以应用拓展欧几里得，再加上 \(x_1,x_2\) 通解的线性关系进行求解，但是这种方法在 \(N=3\) 就失效了，因为只有整数特解，难以获得正整数解。
巧思就是提出一个 \(V_N\)，然后用它划分同余类，最后再加上若干 \(V_N\) 达到 \(S\)，这大幅缩减了数据范围，从而我们可以用最短路来实现转移，维护的就是用 \(V_1\) 到 \(V_k\) 之间的项，使用 \(i\) 种颜色到达这个模 \(V_N\) 同余类的最小值，同时还要维护当前颜色是否出现过，这个好办，预处理的时候把颜色排序，每次更改颜色就把出现过的都挪到没出现的项里面就行。