COCI 2023.11
LOJ3999
考虑把填数过程倒过来做，那么就变成了覆盖。
设 \(f(i,j,0/1)\) 表示目前填进去 \(i\) 个数，且最后一个填的数是 \(j\)，并且 \(j\) 的位置在最左侧/最右侧的方案数。以 \(f(i,j,0)\) 为例，转移有：
- \(f(i,j,0)\to f(i+1,k,0)\)，要求 \(k\le j-1\) 且 \(j-1\equiv k\pmod 2\)。
- \(f(i,j,0)\to f(i+1,k,1)\)，要求 \(k\le j-i\) 且 \(j-i\equiv k\pmod 2\)。
前缀和优化即可，复杂度 \(O(n^2)\)。
LOJ4000
考虑建一个 DFS 树，那么非树边都是返祖边。
考虑 \((u,v)\) 这样一条非树边，这里 \(u\) 是 \(v\) 的祖先。在删掉 \(u\) 和 \(v\) 之后图长这样：
这里紫色部分和红色部分都可能不存在，但由于我们限定这是一条非树边因此绿色部分一定存在。\(u\) 上面的部分也可能不存在，但稍后我们会看到这并不影响判断，
首先红色部分必须存在向上的连边否则就会和绿色部分分开。因此我们可以把红色部分和 \(u\) 上面的部分看作一个整体。当 \(u\) 为根节点的时候红色部分不存在，不过这不会影响我们的判断。
注意到绿色部分也是一个整体的连通块，紫色部分会构成若干连通块。那么紫色部分的每个子树要么和绿色部分有连边，要么和红色部分有连边（且红色部分存在）。我们分几类情况讨论：
- 存在一个紫色的子树和红绿均无连边：这个子树会被分割为独立的一个连通块，一定不合法。
- 存在一个紫色的子树同时和红绿均有连边（且红色部分存在）：（在判掉上面那种情况的前提下）一定合法。
- 每个紫色的子树都只和红色或绿色中的一个连边：这时需要绿色部分和红色部分有连边，或者红色部分不存在。
考虑三种情况怎么判，发现只需要维护某个子树内最浅和最深的一条返祖边，可以用线段树合并或启发式合并求出。对于第三种情况，绿色部分可以写成 DFS 序上的 \(O(1)\) 个连续段，维护 DFS 序区间最小值即可。对于求出绿色部分顶端的点，发现本质上是树上 \(k\) 级祖先。
接下来我们考虑树边怎么判。设 \(u=fa_v\)，有以下情况：
- \(u\) 是根节点：如果 \(u\) 在 DFS 树上的儿子数量 \(\ge 3\) 一定无解，如果 \(u\) 在 DFS 树上的儿子数量 \(=2\) 那么要求 \(v\) 在删去 \(u\) 之后是一个孤立点。如果 \(u\) 在 DFS 树上的儿子只有 \(v\)，那么这要求 \(v\) 在 DFS 树上也只有一个儿子，或者 \(v\) 是孤立点。
- \(u\) 不是根节点：要求 \(u\) 的除了 \(v\) 的每个儿子都得有向上的连边，然后如果 \(v\) 有儿子就必须连到 \(u\) 的祖先上。
时间复杂度：\(O(m\log n)\) 或 \(O(m\log^2n)\)。
THUPC2023
H
\(w(i,j)=\log_2\text{lowbit}(i\oplus j)\)
D
显然 \(10^L\) 是一个合法解，于是答案不超过 \(10^L\)，而 check 是容易的。
枚举答案，然后 \(O(10^L\times N)\) 做完了。
A
考虑到附加边一共不会经过超过 \(k\) 条，但这个是为啥来着不会证了啊
然后可以分 \(k\) 个阶段做，每个阶段先对正常边跑 dij，然后需要做类似于 \(f_x+a_{\text{popcount}(x\oplus y)}\to f_y\) 这样的一个转移。这个考虑类似 fwt，依次考虑每一位，\(g(i,j,S)\) 表示这个数是 \(S\)，考虑了前 \(i\) 位，目前 popcount 已经有 \(j\) 位不同，这种情况下 \(f\) 的最小值。那么转移就是
\[g(i,j,S)\to g(i+1,j,S)\\ g(i,j,S)\to g(i+1,j+1,S\oplus 2^{i+1}) \]最后用 \(\min_j g(k,j,S)+a_j\) 来更新 \(f_j\) 就行了。
K
打表发现 \(\text{SG}_i=i\)
需要求
\[\sum_{x+y<M,x\ge 0,y\ge 0}[S\oplus M\oplus x\oplus y=0]+\sum_{i=1}^N\sum_{x+y<i,x\ge 0,y\ge 0}[S\oplus i\oplus x\oplus y=0] \]设 \(f(N)=\sum_{i=1}^N\sum_{x+y<i,x\ge 0,y\ge 0}[S\oplus i\oplus x\oplus y=0]\) 那么上面就是 \(f(N)+f(M)-f(M-1)\)
考虑
\[\begin{aligned} f(N)&=\sum_{i=1}^N\sum_{x+y<i,x\ge 0,y\ge 0}[S\oplus i\oplus x\oplus y=0]\\ &=\sum_{x,y\ge 0,z>0}[x\oplus y\oplus (x+y+z)=S,x+y+z\le N] \end{aligned} \]从低位向高位 DP，\(f(i,j,k,l)\) 表示在第 \(i\) 位，前面进位传过来一个 \(j\)，\(k=0/1\) 表示目前和 \(N\) 的大小关系（\(>,=,<\)），\(z\) 是否有非零的位。
F
题目的约束相当于：对每个 \(1\le i,j\le n\)，都有
\[\sum_{k=1}^na_{i,k}b_{k,j}=a_{i,j}b_{i,j} \]发现 \(b\) 的每一列是独立的。这里加法可以看作 xor。
依次考虑每一列，如果当前在第 \(p\) 列，那么有以下方程组：
\[\sum_{k=1}^na_{i,k}b_{k,p}=a_{i,p}b_{i,p} \]其中 \(i=1,2,\cdots,n\)。移项就可以得到一个右侧常数均为 \(0\) 的方程组，其系数矩阵形如
\[\begin{bmatrix} a_{1,1}-a_{1,p}&a_{1,2}&\cdots&a_{1,n}\\ a_{2,1}&a_{2,2}-a_{2,p}&\cdots&a_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}-a_{n,p} \end{bmatrix} \]这里减法也是 xor。然后由于 \(a\) 是随机的，可以证明这样的矩阵自由元很少。
\((n-1) \times n\) 矩阵秩为 \(n-1-k\) 的概率可以这样估计，考虑这些向量都在对应的空间中的概率为 \(\frac{1}{2^{kn}}\)，而这样的空间数量和零空间数量相同，后者可以用零空间的任意张成组来简单估计上界为 \(\binom{2^n}{k}\)，因此是 \(O(\frac{1}{k!})\) 级别的。
那么每一行解数很少，可以暴力处理出所有解。
还需要满足恰好有 \(k\) 个 \(1\)，那么背包即可。使用 bitset 优化消元，复杂度 \(O(\frac{n^4}{w})\)。
L
EC-Final 2021
B
首先算出 \(f(l,r)\) 表示 \(j\ge i>r+1\)，且 \(s[i\cdots j]=s[l\cdots r]\) 的 \((i,j)\) 个数。
这个可以 sam，依次考虑每个节点，算出来 endpos 然后考虑每个长度，然后双指针。
有了 \(f\) 之后考虑枚举 \(s_2+s_3\) 的左端点 \(p\)，然后枚举 \(s_1\) 的左端点 \(q\)，可以发现这个首先需要满足一个 \(s[q\cdots p-1]=s[p\cdots 2p-q-1]\)，然后我们就可以给答案加上 \(\sum_{j\ge 2p-q}f(p,j)\)。维护 $f(p,\cdot) $ 的后缀和即可。复杂度 \(O(n^2)\)，疑似可以继续优化
G
首先把能确定的位置 bfs 一遍都确定下来，然后如果还有空位，随便选一个填上接着 bfs。
D
显然答案不超过 \(2\)。
考虑 \(0\) 怎么判，发现需要判线段与线段相交。
考虑 \(1\) 怎么判，发现大概需要判一些半平面的交和并是否非空之类的。
被卡精度了牛魔酬宾
CCPC 2021 Guilin
A
答案是 \(2x-1\)，注意开 long long
I
从大到小贪心
G
二分答案后判一下，需要特判 \(n=1\)
E
发现不管怎样，第一次我们删所有 \(i<j\) 的边 \(i\to j\)，第二次删 \(i>j\) 的一定能删完。
于是 \(ans\le 2\)，发现 \(ans=1\) 当且仅当无环，\(ans=0\) 需要图中没边。于是只需要求有向图最小环。
J
可以先 SA 对每个 \(i\) 求出长为 \(i\) 的本质不同子串个数，然后就变成了查询长为 \(i\) 的本质不同子串中字典序第 \(x\) 小的一个。考虑离线，从大到小做，把 \(h_i\ge k\) 的位置 \(i\) 连边 \((i,i+1)\)，那么会形成若干连通块，我们需要支持查询第 \(k\) 个连通块中 sa 的 min。来点 ds 维护下就行。
当然还要删掉长度不够的后缀。
F
考虑算小凸包的每条边被看到的概率，发现只需要求出这条边所在直线和大凸包的交点。
毛估估一下发现交点在大凸包上的位置有单调性，双指针即可。有一些细节。
沙伯出题人卡我精度，精神过题法，启动！
XXII Open Cup, Grand Prix of IMO
E
考虑如果存在 \(i\) 使得 \(2\nmid \text{deg}_i\)，那么这样的 \(i\) 至少有两个，且一定是偶数个。称这样的 \(i\) 为奇点。
考虑随机把点集划分为 \(S,T\)，并考虑 \(S,T\) 之间的边数。发现如果左侧分了奇数个奇点，那么右侧也肯定会分奇数个奇点。但如果删掉 \(S,T\) 之间的边，那么左右两侧必须都要有偶数个奇点。
在删掉 \(S,T\) 之间的边之后，\(S\) 中会有一些偶点变成奇点（这意味着在它的邻边中删掉了奇数条边），也会有一些奇点变成偶点（也是删掉相邻的奇数条边），发现不管怎么变对中间的边的奇偶性影响都是 \(1\)。由于一开始有奇数个奇点，最后变成了偶数个奇点，因此总的奇偶性变化量一定是 \(1\)。
也就是说只要一侧分了奇数个奇点那么 \(S,T\) 之间的边数就是奇数，那么只要存在奇点，随机一组 \((S,T)\) 使得中间边数是奇数的概率就是 \(\frac{1}{2}\)。
考虑怎么算 \(S,T\) 之间的边数，先算总边数再减掉 \(S,T\) 各自的边数即可。这样可以先用 \(1\) 次询问得到总边数，然后再用 \(29\times 2\) 次询问 check \(29\) 次，这样错误率就是 \(\frac{1}{2^{29}}\)。
B
考虑 \(\lfloor x/w\rfloor =\frac{1}{w}(x-(x\bmod w))\)，考虑维护 \(\sum x\) 和 \(\sum (x\bmod w)\)。
用平衡树维护排序之后的序列，那么每次相当于单点插入和单点删除。
对于每个节点，维护其长度 \(L\)，发现需要维护 \(\sum i^ka_i\) 以及 \(\sum \left(\left((i\bmod w)^ka_i\right)\bmod w\right)\)。
对于第一个，维护 \(S_j=\sum i^ja_i\)，那么合并的时候需要把右边的信息位移一下变成
\[\sum_{i=1}^La_i(i+p)^k=\sum_{i=1}^La_i\sum_{j=0}^ki^{k-j}p^j\binom{k}{j}=\sum_{j=0}^kp^j\binom{k}{j}\sum_{i=1}^La_i\times i^{k-j}=\sum_{j=0}^kp^j\binom{k}{j}S_{k-j} \]于是可以 \(O(k^2)\) 合并。大概还需要预处理快速幂。对于第二种维护
\[T_{x,y}=\sum_{i=1}^L[i\bmod w=x,a_i\bmod w=y] \]那么答案就是 \(\sum_{x,y} \left(\left(x^k\times y\right)\bmod w\right)\times T_{x,y}\)。合并的时候需要在 \(x\) 这一维上偏移一下。
总复杂度 \(O(n(k^2+w^2)\log n)\)。
H
先判掉 \(K=1,K=2\)。首先 \(K\le 20\) 的时候可以直接输出一个 \(K\) 个点的环。
现在是找规律时间！下面为了方便我们把图改成 0-indexed。
- 在 \(n=20\) 个点的环上加一条边 \((0,2)\)，可以得到一个 \(ans=22\) 的解。
- 进一步再加 \((2,4)\)，\(ans\) 会 \(+1\)；依次类推，除了最后一个 \((18,0)\) 不会使 \(ans\) 改变之外，其他的 \((2i,(2i+2)\bmod n)\) 这些边都会使 \(ans+1\)。
- 现在我们可以得到 \(ans=30\) 的图，类似地添加 \((2i,(2i+4)\bmod n)\)，可以得到 \(ans=32,33,\cdots,39,40,40\) 的图。
- 类似地添加 \((2i,(2i+6)\bmod n),(2i,(2i+8)\bmod n)\) 就可以得到 \(ans\le 60\) 的图。
- 注意 \(21,31,41,51\) 这四种情况上面构不出来，需要特殊处理。具体来说 \(ans=21\) 就直接令 \(n=19\) 再加 \((0,2)\)，其他的都是删掉上一个阶段的最后两条边再提前加入下一个阶段的一条边。
于是就做完了。
看了官方题解之后发现我做麻烦了orz
I
对每个 \((i,j)\)，如果第 \(i\) 个矩形和第 \(j\) 个矩形有交我们就连边 \((i,j)\)，那么要数的就是补图三元环个数。发现补图三元环个数不好数，设 \(x,y\) 分别为原图三元环个数和补图三元环个数，一般地，有
\[2(x+y)=\binom{n}{3}-\sum_{i=1}^n\binom{\deg_i}{2}-\sum_{i=1}^n\binom{n-\text{deg}_i-1}{2} \]现在只需要算 \(\text{deg}_{1\cdots n}\) 以及原图三元环个数。
考虑怎么算 \(\text{deg}_i\)：按照右边界排序，先钦定 \(i\) 的右边界在 \(j\) 的右边界的右侧，那么 \(x\) 这一维上和 \(i\) 相交的矩形 \(j\) 形成一个区间，现在需要算这个区间内有多少个矩形在 \(y\) 这一维上也相交。容斥，设 \(i\) 的上下边界为 \([s,t]\)，用总数减去上边界 \(<s\) 和下边界 \(>t\) 的即可。发现是二维偏序，可以离线后树状数组或者直接主席树。
考虑怎么算三元环：先考虑一维的情形，考虑 V-E 容斥，钦定一个 \(i\) 被三个都包含算一下方案数，再钦定 \((i,i+1)\) 同时被包含算一下方案数，这样恰好把每个计数一遍。那么二维就是两边分别做一下这东西，扫描线即可。需要线段树维护区间的 \(\binom{a_i}{3}\) 以及 \(\binom{a_i}{2}\) 之和，以及区间加。
总复杂度 \(O(n\log n)\) 带巨大常数。
K
首先一个 \(3\log_2K\) 的方案：考虑当前方案数为 \(x\)，加一个 \(0\) 可以 \(x\leftarrow 2x\)，然后考虑如果当前集合中《所有正数之和》与《所有负数之和的绝对值》中的较大值为 \(S\)，那么我们考虑同时加入 \(S+1,-(S+1)\)，可以令 \(x\leftarrow x+1\)。于是这样就不超过 \(3\log_2K\)。 但是过不去。
考虑随一个正整数集合 \(S\)，设 \(x=\max(S)\)，我们加一些 \(\le -x\) 的负数进去，那么加一个 \(x\) 对方案数造成的贡献就是正数凑出来 \(S\) 的方案数。做一个背包就行。
具体来说我们 DP 算出来 \(f_i\) 表示凑出来 \(i\) 所需的最小个数，同时 \(g_i\) 表示 \(i\) 的前驱，这样就能构造方案了。
如果随出来的 \(S\) 不行就再凹两下，直到凹出来一个能覆盖 \([1,10^6]\)。反正这些都可以预处理，所以凹多少次才出分都无所谓，硬凹就行了（
The 2nd Universal cup. Stage 13
B
显然 \(p,q\) 之间是双射。考虑一位一位地确定 \(p\)，如果现在在填 \(p_i\)，那么相当于我们在 \(q\) 里面的一些位置填入了 \(1,2,\cdots,i\) 这些数，然后问能够让 \(q\) 满足他那个条件的方案数。由于填入的是最小的 \(i\) 个，所以后面再填都只会更大，所以算出来每段方案数然后合并一下就行了。复杂度大概是 \(O(n^3)\)。
官方题解怎么是 \(O(n^5)\) 啊？我能做 1e6 啊。
M
首先发现 \(s\to t\) 等价于 \(0\to (s\oplus t)\)。考虑 \(0\) 开始的一条路径。
发现很有规律，大概是有这样的循环：
00
01
11
10
00
打表发现终点是 \(0\) 的答案是 \(\frac{4}{3}(4^{k-1}-1)\)
预处理一下步数之类的东西，然后大概在一个类似 trie 的东西上走一趟就行了
2023.12.11
A
首先可以发现一些事实：如果染色的过程形成了连续段，那么连续段长度都得一样，而且连续段之间的间隔也得是连续段长度的倍数。设 \(f(h,n)\) 表示连续段长度 \(>1\) 的答案，\(g(n,k)\) 表示连续段长度 \(=1\) 的答案，就有
\[f(h,n)=\sum_{k\mid n,k>1}g(h/k,n/k) \]然后：
- 通过找规律发现 \(g(h,n)=f(h,h/n)\)，有了这个结论之后就有
边界是 \(h(\cdot,1)=1\)。这个时候暴力递推就可以过了。
然后也可以优化，具体就是对每次除掉的 \(k_1,k_2\) 计数，二项式反演之后多点求值就可以 \(O(N\log ^2N)\) 其中 \(N\) 是 \(h\) 的所有质因子次幂和。可以不用多点求值做 \(O(N\sqrt{N})\)，但是还是要 fft。这部分比较 trivial。。。
然后我们来证一下 \(g(h,n)=f(h,h/n)\)，大概是说把 \(d\) 看成一个 \(P(x)=\sum x^{p_i}\) 这样的一个多项式，其中 \(p_i=\sum_{j<i}d_j,i=1,2,\cdots,n\)，然后相当于是得存在一个 \(Q(x)=\sum x^{q_i}\) 使得 \(P(x)Q(x)=\sum_{i=0}^{h-1}x^i\)，然后我们把对 \(P\) 计数改成对 \(Q\) 计数，发现 \(Q\) 刚好就是所有连续段长度 \(>1\) 的情况。
B
考虑 rprmq1 的做法：对一维建线段树之后，矩形 max 就变成了 \(O(\log n)\) 个顶着左边界的矩形 querymax，对于这种可以直接考虑扫描线，线段树维护区间历史最大值。这个是 ez 的。
那现在他其实是相当于把一维强制在线了，不过我们可以二进制分组，维护每一组结束到当前时刻的线段树，以及这一组内部的 query 区间到这一组的结束时间这段矩形的 max。每次就在每个组的线段树上暴力修改一下。那么还有合并两个组的操作，这个就直接暴力更新一下 mx，然后清空掉前面那个组的线段树就行。清空也得维护一个标记，非常的抽象
还有一个做法是说在线段树每个节点上维护一个单调栈，考虑一次查询其实是说要查询 \(O(\log n)\) 个节点的单调栈上面，时间 \(\ge t\) 的一个历史最大值。然后我们的操作可能会合并出来 (add,maxadd) 这样的标记，合并到单调栈上就是把当前的 \(mx+maxadd\) 再插入单调栈。然后插入守望者就是在这 \(O(\log n)\) 个节点里面各自插入一个。
C
LuoguP6816
写了 10k 代码，这题真不好评价。。
2023.12.12
A
Luogu9084
大概来说，先考虑怎么算答案，发现建出笛卡尔树之后是简单的；再对着这个 DP 即可。
需要设 \(f(i,j),g(i,j)\) 表示 \(i\) 个数的排列 \(ans=j\) 的方案数，其中 \(f\) 认为排列最左侧有一个 \(n+1\) 也就是无论如何都会删去最左侧的数，\(g\) 认为左右两侧都有一个 \(n+1\)。最后算答案把 \(f\) 合并起来即可。
每次至少删掉一半的数，因此 \(m=O(\log n)\)，将转移用前缀和优化可得复杂度为 \(O(n^2\log n)\)。
B
Luogu3581
考虑从小往大插入每个数，那么任意时刻不能出现两个数的差 \(>L\)。
维护当前 \(n-L+1,n-L+2,\cdots,n\) 的相对顺序以及是否相邻即可。
对于本题，\(L=3\)，因此有 \(3!+\binom{3}{2}\times 2!=12\) 种状态，实际上可以发现如果只剩两个数那么必然含有 \(n\)，因此实际的状态数为 \(10\)。
C
树上邻域数颜色。
做法：考虑直接上点分树，发现直接做邻域数点会算重。对每种颜色 \(c\) 建出虚树，然后类似 BZOJ 世界树，对每个点 \(x\) 可以算出所有的 \(v\) 满足 \(v\) 和颜色为 \(c\) 的点中距离最小的一个点恰好是 \(x\) 的这样的所有 \(v\)，我们用 \(x\) 去支配这些 \(v\)，算的时候只能算 \(x\) 的贡献。这样的 \(v\) 在 DFS 序上会形成 \(O(1)\) 段区间。
这里虚树上可能有一些点是新加进来的没有颜色，我们算出这个点到最近的一个有颜色的点的距离 \(d\)，然后把这个点造成贡献的条件 \(+d\)。
然后就变成简单的数点了，把询问挂在点分树上，对每个点单独算一下就行了大概。
复杂度是 \(O(n\log^2n)\)。
标签：log,bmod,2023.12,into,down,cdots,ans,考虑,sum From： https://www.cnblogs.com/YunQianQwQ/p/17898622.html