records on
实际上，如同 title 所说的，从现在开始，将要开始记录。
2022-3-24
发现了，如果是合法解的话，那么一定可以拆分成下图这样的。
后面的可以随便×个 \(2^k\)。
前面要求那个不到 \(0\) 的子序列 \(B\) 要大于后面最大的。
其实后面的我们可以直接看成 \(B\) 把后面的全连起来了。
然后首先考虑怎么求，能划分成两个下降子序列的排列的个数。
往后面加数真的不是很容易，那么不妨考虑按值域枚举，一个一个插入。这个很关键。
这样，你考虑一下最后一个数能插到的地方，显然是一个连续段，所以不妨设dp状态。
\(f_{i,j}\) 表示插入了 \(i\) 个，产生的最后连续段长度是 \(j\)。你会发现我们如果向最后插入，我们钦定了第一个子序列必须选。
所以转移 \(f_{i,j}=\sum f_{i-1,k},k\geq j-1\)。
所以化成后缀和，就变成了组合数（卡特兰），就完事了。
2022-3-24 这个codeforces 感觉挺可惜的，但实际上我觉得主要还是自己没有特别熟悉cf，找一找手感，估计会好起来的。
训练量太少了。
怎么就突然 2022-3-27了。。。。。
2022-3-25 的 T3
题目大意：一个树有两种颜色，每次修改操作为：一个颜色连通块+w,翻转一个点的颜色，链，子树+w，以及询问x所在连通块max。
和我最开始的预期差不多，链和子树可以轻易的使用重链剖分解决。
那么思考一下如何颜色相同连通块+,求max。
我们可以发现，对于一个树连通块，一定有一个顶点，那么所有修改的点都是这个点子树内的。
当然除了一些异色点分开了一些子树的话。
现在我们需要思考如何刻画在同一个联通块内的。
可以发现就是这个点到根异色点个数，就能很好描述这件事。
实际上，我们需要在x的子树内，将num等于num[x]的点全部修改。
这样我们本质上 [sz[x],sz[x]+dfn[x]-1] 上内的num[x]=num[v]的v进行修改。
这是不好改的，但是你发现 num[x]=num[v] 本质上也就是 num[x]=min。
这样是可以做的，但是注意我们一九需要 修改num[x] 所以我们pushdown的时候改变一下策略，先把 num 的tag pushdown这样可以保证现在p的num，和son[p] 的num是绝对正确的。
反过来想如果这个有tag的话，那么说明这个区间自从打tag开始就没有被修改了。
这么做的正确性便有了保障。
和xsy上一道题很像。。。。
约数的根号和？
这个大概就可以分析，因为sqrt积性，显然。。。 \[ \begin{aligned} \prod_i\sum_{j\leq a_i}(\sqrt {p^j})<\prod_{i}\frac{\sqrt{p^{a_i+1}}}{\sqrt{p}-1}=\sqrt n\prod \frac{\sqrt{p}}{\sqrt p-1}\\ \end{aligned} \] 后面那个不是很会分析/kk,按照邓老师说的可能是（？）\(\mathrm{polylog}\) 级别的？
挺水的，大概树和基环树唯一差别，只是多了一条可能有贡献的边。
我们就枚举这个边的贡献，完事了，simple 换根dp......其实挺复杂的。
T3 很简单 f就是卡特兰，然后问你让 \(\binom{2n}{n}\) 的 \(7\) 因子最大化。
我们都知道 \(\binom{n}{m}\) 的 \(p\) 因子个数是 \(n+(n-m)\) \(p\) 进制下的进位数，所以换言之，我们要找到 \(l\leq x\leq r\) 使得 \(2x\) 进位数最多。
你可以贪心找到 \(l,r\) 的lcp后一位，接下来有两种选择。
- xxxxxxx (\(l_k-1\)) 666666666666666666666 这样的
- xxxxxxx(\(l_k\))3333333333333333333333334这样的
我们考虑 1 是普遍都有的。
2需要我们在找到前缀3，看下一位是否>=4。
比较卡我的地方是 高精度换进制。。。。。
复杂度 \(O(n^2/12)\) 当然是12个压一位，然后mod 7 直接加起来%7即可了。
T2 是原题。
大概就是先写出dp：(\(f_{i,j}\) 表示当你在i节点t时刻的最小期望长度) \[ f_{i,j}=\min{(f_{0,0}+j,\sum_{y,l\leq s\leq r}f_{y,j+s}\times p)} \] 含义是当前状态你可以选择会到初始情况。也可以继续走下去。
不能dp的主要原因是 \(f_{0,0}\) 很讨厌
然后这种题的思路就是你把 \(f_{0,0}\) 看成类似主元的东东。然后你分析一下你的 如果你设 \(x=f_{0,0}\)，那么把转移的 \(f_{0,0}\)改成 \(x\) 后的,\(f_{0,0}\) 实际上是一个一次函数，实际上如果你考虑 所有 \(\min\) 的情况，他其实是一个直线取 min 也就是下凸壳。
我们实际上也是想解方程 \(F(x)=x\) 这种的。你考虑实际含义只能有一个解，那么直线与凸壳交点也只能有一个了，可以二分。
T1
。。。。我竟然忘记了点分治。
重写一下点分治用途，点分治可以将经过一个点的链，分成 \(\log\) 级别种。所以在处理链问题，点分治有奇效。。。
2022-4-26？
待修改的整体二分？我们那就得按照时间来自然定序了，考虑的时候并不是cdq，当前我们找到了答案 \([l,r]\) ，而操作时间区间为 \([ql,qr]\)，那么对于一个 \(i\) 询问，我们只考虑前面当前合法的 (\([v_j\leq mid]\)) 的算上贡献，如果此时贡献足够了说明进到左递归区间，那就直接进入。
如果不够那说明进入有区间，注意右区间的都是 \(>mid\) 的此时必须将 \(\leq mid\) 贡献消去，并且由于天然的时间序，进入左侧的不可能也不应该贡献到这个询问。。
4-10
这个题，，主要的key是你看到有K个不同要第一时间想起差分。
没错，现在变成每次 \(\text{xor}\) 一个 \(\text{popcount}=k\) 的数。
所有数都可以被表示成 一个集合 \(S\) ，\(x=\sum_{z\in S}\oplus z\)。现在是想便利这 \(2^n\) 个状态，是每一次只改变一个。
倍增构造即可，本质上实在k维空间便利，你画一画三位什么的就容易了。
[ZJOI2010] 排列计数
我们容易建出一颗限制的树。这是一个二叉树。，可以发现一个点的左子树右子树是无关的，所以限制在一个点合并两个子树，实际上就是有标号合并。如果发现这点dp显然了。
[SCOI2010]幸运数字
其实一眼容斥，我们实际上就是找出 \(S\subset U,\mathrm{lcm}(S)\) 这种东西。
实际上幸运数字是 \(O(2^l)\) 级别的。
这个只是分析，并不严谨的放缩，为我们先假设 \(lcm(a,b)=a\times b\)，那么我们设这个集合里的串的长度和大概和 \(n\) 差不多，所以实际上，合法的 \(lcm(S)\) 的个数是类似划分数的，很少的。并且我们对于一种划分方式，我们构造出来的也只不过是 \(2^{l_i}\) 这种的。所以容斥其实复杂度可以接受，
现在我们只需要找出这些 \(lcm(S)\) 这个复杂度，就很迷惑了，不好分析，通过一些不那么优秀的爆搜，也可以看出实际上我们需要的 \(lcm(S)\) 甚至只有 \(10^4,10^5\) 左右的。
但是并没有题解给出非爆搜做法，我也并不会别的非爆搜做法，，，
所以只能爆搜了，。。。。爆搜最重要的trick 是，你要枚举一个上升序列 \(\prod a_i<n\) 你不如枚举一个下降序列 \(\prod a_i<n\) ，原因是你合法的时候代价一样，不合法的时候，对于一个状态肯定是前缀更有可能 \(>n\) ，所以要倒着枚举。
这个题一言难尽呀。
我其实不是很认可一些”理所当然“的二项式反演。
所以给出一种更加复杂的做法。。。很拉。
首先我们肯定是要做 \(n\) 个元素的集合，交集大小是\(m\) 的个数，我们可以选出 \(m\) 个地方，然后问题变成了 \(n-m\) 个元素的集合，交集大小是 \(0\) 的选几个方案个数。 \[ f_n=2^{2^n}-1-\sum_{i\leq n}\binom{n}{i}f_{n-i} \] 值得注意的是 \(2^{2^n}\) 要减去1，也就是空集情况。含义就是简单的容斥。
这么求解下去肯定是没出路的，显然移项然后二项式反演。
简单推导得到 ： \[ f_n=\sum_{i\leq n} \binom{n}{i}(-1)^{n-i}(2^{2^i}-1) \] 然后问题变成 \(4\mid i\) 的求解，也不难想到单位根反演。
\(2^{2^i}-1\) 形式很烂，但是我们发现有 \(-1\) 的轮换系数，实际上实在抵消的。（当然在 \(n=0\) 并不会抵消，伏笔 ）
写出式子： \[ \begin{aligned} \sum_{i\leq n,4\mid n-i}\binom{n}{i}\sum_{j\leq i} \binom{i}{j}(-1)^{i-j}2^{2^j}\\ \sum_{i\leq n}\sum_{1\leq t\leq 3}\epsilon^{t(n-i)}\binom{n}{i}\sum_{j\leq i} \binom{i}{j}(-1)^{i-j}2^{2^j}\\ \sum_{1\leq t\leq 3}\sum_{j\leq n}2^{2^j}\sum_{i\geq j}\binom{n}{i} \binom{i}{j}(-1)^{i-j}\epsilon^{t(n-i)}\\ \sum_{1\leq t\leq 3}\sum_{j\leq n}2^{2^j}\sum_{i\leq n-j}\binom{n}{i+j} \binom{i+j}{j}(-1)^{i}\epsilon^{t(n-i-j)}\\ \sum_{1\leq t\leq 3}\sum_{j\leq n}2^{2^j}\binom{n}{j}\sum_{i\leq n-j}\binom{n-j}{i} (-1)^{i}\epsilon^{t(n-i-j)}\\ \sum_{1\leq t\leq 3}\sum_{j\leq n}2^{2^j}\epsilon^{t(n-j)}\binom{n}{j}((-\epsilon^{-t}){^{i}}+1)^{n-j}\\ \end{aligned} \] \(O(n)\) 计算即可，实际上这个 \(\epsilon\) 就是 \(\mathrm{i}\) ，或者说是 \(-1\) 在 \(\bmod 998244353\) 下的平方根。原根pow一下就好。
2022-4-11 模拟赛
T2 简单的 min25筛，\(\mathrm {minp}\) 这个转移只有两条边，一种直接 \(\times\phi\) ,一种加上 \(\sigma_1\)，直接维护两个东东就好了。
P.S. 递推版的min25确实慢死，我甚至怀疑他是不是 \(\mathrm{soft }\ O(n^{3/4})\) 什么的。。。
所以不如直接爆搜。。。。
T1 我觉得有点难？
排列很好说，我都看出来了逆序对是偶数是充要的，然后序列你就考虑你先把这个东西看成排列（重标号），如果本身就是偶数，必然合法，如果是奇数，也很简单，你进行一次移动 \(ab\) 但是经过 \(a\) 这种，你会发现此时逆序对 -1（1,1移动后不会贡献），所以不难发现序列一定有解。
没想出来本质上就是没看出来性质。。。。。。主要是你要发现实际上挪动两个可以看成一步一步挪动这两个，然后实际上你只不过将一个移动两步，这样你可以类似冒泡那样，把前 \(n-2\) 个冒泡排好序，那么也就剩下了最后那两个，得出逆序对为偶数，序列也好考虑类似上文那样。
剩下直接 dp 不易，但是别忘了你的系数有特点第 \(i\) 个数，只能填到 \(i+1\) 个位置，那么确定状态也简单了，你可以直接将空出的位置设入状态。
T3 鸽子了
\(\tau\)
OSU
首先拆开贡献，\(1\) 自己一组，发现 \(L^2+L\) 可以理解成 \(L\) 段内选 \(i,j(i\leq j)\) 的概率和。
所以问题转化为怎么算 \(w(i,j),([i,j]\subset [l,r])\)，其中 \(w(i,j)=\prod p_k\) 。
题解给出了矩阵维护这个东西。。。。。。。我觉得很神。
但是实际上，区间的子区间，，这个东西可以分治（线段树），考虑线段树怎么合并即可了（分治，左节点，右节点，跨块的（lsum,rsum））。
地震后的幻想乡
先说我的另类解法。
首先我的转化是将期望转化为 概率，也就是最小生成树最大边 <=x 的概率的和。
此时问题转化为了，对于 \(x\) ,如果一条边权 \(\leq x\) 保留，否则删掉，问最后联通的概率。
我是这样想的，实际上本质不同的联通情况是少的。
我大概就是在容斥，，首先加上系数 \(\times\) 钦定一个连通块的概率 加上 系数 \(\times\) 钦定两个连通块的概率......
而钦定k个连通块的概率就是，把跨块的边只能是 [x,1] 所以贡献是 \(x^{num}\)。
所以我们枚举联通情况，维护出多项式，最后积分。
只剩下如何求容斥系数了。
| 钦定的连通块个数 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 容斥系数 | 1 | -1 | 2 | -6 |
可以看出是 \((-1)^nn!\)，我是考虑钦定为 \(n\) 的情况，会被 \(\begin{bmatrix}n\\j\end{bmatrix}\) 个钦定为 \(j\) 的算贡献。
所以系数的递推式： \[ \begin{aligned} f_i=-\sum f_j\times s(i,j)\\ \end{aligned} \] 不会证明。。。可能是斯特林反演惊恐
soulist做法。实际上和这个大同小异了。。。。。
我们要求出 \(\leq x\) 的连通子图概率和。这个可以DP。
设 \(\mathrm{dp}(s,i)\) \(s\) 表示和 \(1\) 联通的情况, \(i\) 表示这个状态选了几条边。
我们考虑容斥，先在 \(s\) 这个集合随意选边 也就是 \(\mathrm{dp(s,i)}\) 初始化为 \(\binom{edge(s)}{i}\)。
然后枚举包含 \(1\) 的极大集合，减去，其中补集边随意选即可。
清新的厉害题 cf68D
不知道怎么描述。。。就说这样一个“尽管我发现了但没做出来的”observation。
若 \(lv<rv\) 那么说明断 \(ls\) 边的答案可以确定了，只需要进一步考察断 \(rs\) 边的答案。
反之同理，特别的 \(lv=rv\) 说明无论断 \(ls\) 还是 \(rs\) 答案都知道了。
这样随意维护课做到 查询 \(O(h^2)\) 的复杂度。。。。。
入门DS题 simple rmq
看了题解。。。。首先，经典套路是维护每一个 \(r\) 结尾的答案。
考虑一个 \(x_i\) 有贡献的区间是 \([pre_i+1,i]\) 这样的区间。当然我们需要下一个 等于 \(x_i\) 的数出现时删掉贡献。
出现的时间是一个区间。离线固然好直接时间分治。
在线吗，那就使用主席树记录一下每一个 \(r\) 的信息，然后区间修改什么的即可。（维护max,区间取 max 不用 seg beats）
复杂度 \(O(n\log^2 n)\)。
随机游走相关。
- 设状态为到 \(x\) 停止的期望长度，容易dp
- 如果可以一直走，然后有一个终止位置集合，那么概率可以设成所有时刻，在这个点的概率，这样，初始起点集合只需要 讲转移式子 \(+1\) 就好。
- 网格图的主元法实际上，就是先进行了若干步“带入消元”，使得最后答案都表示成 主元向量的线性表示。
5,4 模拟赛 A
两个字符集 \(A,B,C\) 然后相邻不同的长度 \(2n+1\) 串使 lcs =n。
主要你要发现，两个长度为2的区间是一定有相同的字符的。
然后你大概能猜到，这样来说，存在下阶 \(n\) 。
然后就是如何构造的问题了。打个表，构造构造就好了。
难点在于 发现下界，以及实现上。
模拟赛B
不是很会。。。。。。。。。。。。。。。。
首先不是很懂为啥要这么考虑，，，，，，感觉很神
就是考虑 \(x\),\(y\) 对不合法区间的贡献。
就是把 z=lca 找出来，然后分讨不合法区间是什么，实际上就是矩形覆盖矩形查1.
然后这个矩形覆盖有特性的，他是接地，和接左的 3-side矩形。
具体问题的话，子区间就很烦，所以转化成对一维进行”扫描线“，每时每刻维护线段树，下标 \(i\) 的含义是以 \(i\) 为左端点，切右端点\(\leq T\) 的区间的答案。
不难发现此时询问变成了对上述线段树的区间询问。
那么如何维护线段树呢，实际上由于 3-side ，一种矩形可以逆着扫，然后变成区间覆盖类似的东西（因为不可能改变了）。每次只给没被覆盖的点加 1 的权值。
另外一种矩形由于有一side接左，所以有贡献的区间一定是一段前缀，这个维护最下面边，然后线段树二分即可。
现在就剩一个问题了，那我们 \(n^2\) 个区间怎么搞。
可以在 \(z\) 统计 \(x,y\) 的贡献。经典dsu on tree，你可以真的启发式合并，然后枚举小的，然后统计大的贡献。
这样区间个数也是 \(O(n\log n)\) 的。能做了。
好疲惫
新航线。
第一题简单博弈，实际上发现白色的线性基只是后缀罢了，没有必要线性基合并等无聊的做法。
复杂度 \(O(n\log w)\)
第二题，离谱的生成函数。
很简单的dp,但是又两种写法。。。。。 \[ \begin{aligned} dp_n=\sum_{i<n}dp_idp_{n-i}\binom{n-1}{i-1}+1\\ dp_n=\frac{1}{2}\sum_{i<n}dp_idp_{n-i}\binom{n}{i}+1\\ \end{aligned} \] 第一种是钦定选第一个，第二种是算重后/2。事实上的确第二种更容易推到。
先说这种分治ntt怎么搞： \[ \begin{aligned} f_n=\sum_{i+j=n,i<n} f_ig_j \end{aligned} \] 若此时 g 不是已知而是通过 f 求出的，怎么分治ntt?
具体是： \[ \begin{aligned} l=0,&f[l,m]\oplus g[l,m]\to h[m+1,r]\\ l\not=0,&f[l,m]\oplus g[0,r-l]\to h[m+1,r]\\ &g[l,m]\oplus f[0,r-l]\to h[m+1,r] \end{aligned} \] 我们需要保证 solve(l,r)先solve(l,mid)后，l到mid是正确的。
除了最左面的那段，剩下的 mid 都应该大于 r-l。
所以最左段让他只贡献 \([0,mid],[0,mid]\) ，剩下的三端之后在贡献。
具体记忆方法是，f,g此时可以看成对称的，所以转移需要对称。
那么如何推到第一种转移的生成函数呢？ \[ \frac{dp_n}{(n-1)!}=\sum\frac{dp_i}{(i-1)!}\frac{dp_{n-i}}{(n-i)!}+\frac{1}{(n-1)!} \] 或许你可能会觉得这个只不过是ogf,设生成函数不过是把ogf换下元。但是事实上
egf具有的组合含义，代数性质要比你瞎设的好得多。
设 \(f_n=\frac{dp_n}{n!}\)。 \[ \begin{aligned} nf_n=\sum if_if_{n-i}+\frac{1}{(n-1)!}\\ xF'=xF'\times F+e^xx\\ \int F'dx=\int F'\times Fdx+\int e^xdx\\ F=\frac{F^2}{2}+e^x \end{aligned} \] 解得：\(F=2-\sqrt {3-2e^x}\)
剩下的就是多项式开根了。
第三题，真拉。
首先问题就是树链 vec*mat。
做法是线段树+树剖。
发现重链剖分后实际上就有一段（最上面的）不是重链前缀。
所以你可以直接按dfn序建线段树。（线段树建树是没有常数的n，只在非叶子节点合并）
然后维护一下每个重链前缀和。
这样查询就是 \(O(q\log n l^2)\)，\(\log\) 个重链，每次 \(O(l^2)\) vec*mat。
最后一个线段树分成 \(\log\) 个区间，每次 \(O(l^2)\) vec*mat。
T1很简单的斜率优化，一直没时间学李超树（待填），，，cdq1log,2log都能过。
T3 为什么数据结构一直没思路呀。。。。。。。。。。。。。。。。。。。。
and 和 or 运算是不太可能 O1 pushdown 计算答案之类的。
那区间修改怎么办呢？那就考虑一下势能把。
我本来傻傻的以为 and or 运算会互相改势能，现在看还是太 naiive了。
我们只考虑改一段区间一直 and 和 Or 一个数会怎样。
and 会给一个子集钦定成 0,or会给一个子集钦定成 1。
所以被钦定的子集只会单调增，这个可以被看成势能。
对于一个区间如果我们让他势能增大我们可以重构他。
那么不难想到：分块 每次会让2个散快势能发生清空 （不是整区间修改），整块就是 \(n/B\) 个每块看势能是否增大，增大就重构。
可以做到根号下log。
也可以线段树，每次会更改 \(O(\log n)\) 个区间。（势能释放），整seg区间看是否增加势能，暴力更新信息。复杂度 2log。
暴力重构看到子区间不增加势能停止即可。否则你甚至会因为常数过大 TLE。
T2，hhz说了看到100这种小范围还不会做，最优化就想flows，计数就想线代det。
我却以为这是最优化，想flows，我是傻逼。
实际上判断性要比计数更简单。
一个二分图完美匹配就是一个置换，不难想到 积和式的意义。
至于我们希望是 k 的倍数的话，就单位根反演。 \[ \begin{aligned} \sum_{p}[k|w(p)]=\sum_{p}\sum_{t<k}w_n^{t\cdot w(p)}=\sum_{t<k}\sum_{p}(w_n^t)^ {\sum c(i,p_i)}=\sum_{t<k,p}\prod (w_n^t)^{c(i,p_i)} \end{aligned} \] 较为标准的积和式。可惜的是我们并不能很快速的计算积和式。
那就那行列式当代替品。但是用行列式当代替品就会出现误判=0的情况，而且有可能是关于单位根的这个多项式是0，这很可怕。
在那行列式代替前，让我们线思考一下单位根反演的本质在干嘛？
他就是在凑系数，换言之我们把 \(w_n^t\) 拆开后乘上一些常数，这并不会影响容斥的结果。
所以我们可以随机一个矩阵 \(A\) 计算 ： \[ \begin{aligned} \sum_{t<k,p}\prod A_{i,p_i}(w_n^t)^{c(i,p_i)} \end{aligned} \] 这样正确性有了保证。
dp专题还在咕咕咕。
好扯淡了。模拟赛 6.4。