About Me

在无数久的 🐦咕咕咕 后一个新博客它建成了！

Topcoder 12505 CharacterBoard

我们考虑如果能够枚举长度，那么每个字符对应回原串的位置就是固定的了，这样我们就可以直接 $26$ 的剩下字符个数次方得到答案。

但是事实上字符串的长度可能到达 $10^9$ ，这么考虑肯定是不行的。但是仔细想一想会发现，对于多数长度，你的 $n \times m \le 100$ 个字符根本不会有冲突。而有冲突的长度，必然是某两个字符之间差距的约数。因此我们直接枚举每两个字符之间的差距，然后枚举这个差距的约数，然后单独计算这些长度即可。剩下的长度直接用等比数列求和。

A 宝石

开场看错题 1.5h ，一直以为不能拿连续 $k$ 个宝石，然后发现 15pts 都不会，直接导致 T3 暴力都没打。。

我们考虑找出第一个位置，使得这个位置的颜色在之前出现过了，那么如果想继续往后选择，就必须把这个位置丢掉。我们一直重复找这种位置的过程，知道找到了第 $k+1$ 个，此时我们就只会在前面的东西种选择 $k$ 个扔掉。具体来说，对于每个出现了大于等于 $2$ 次的颜色我们只会保留最大的。

由于 $k$ 很小，我们可以考虑暴力做上面那个过程。每次之需要找到后面第一个重复出现的颜色即可。具体来说，我们可以记一个 $nxt_i$ 表示下一个与 $i$ 颜色相同的位置，然后我们就只需要找到 $s\sim n$ 中 $nxt_i$ 最小的位置即可。这个可以用线段树来维护 $nxt$ 的区间最小值。

于是我们暴力跳，暴力维护所有出现大于等于 $2$ 次的元素即可。

复杂度 $O(mk\log n)$ 。

懒得卡空间了！

我们考虑对于一段区间来说，在全局加 $x$ 后，长度为 $l$ 的段的最优答案是啥。不难发现是 $lx + b$ ，其中 $b$ 为长度为 $l$ 段的和的最大值。因此我们可以对每个 $l = 1\sim n$ ，求出一条直线，然后对这个直线求一个凸包就可以做询问在全局加 $x$ 的情况下的和了。

然后考虑区间询问怎么办。首先我们可以把区间询问拆成 $O(\log n)$ 个线段树节点。然后对每个节点，我们维护出最大的后缀和，最大的前缀和，最大的区间本身子段，以及区间的和。之需要对这 $O(\log n)$ 个节点做 $dp[u] = pre_u + S_{u-1} + \max_{v < u}(suf_v - S_v)$ 这个东西即可，这个玩意是 $O(\log n)$ 的。所以我们之需要对一个线段树区间维护这几个东西即可。

A 科学怪人

可以发现，只需要求出 $(\frac{n}{\gcd(n,b)},0) , (0,\frac{n}{\gcd(n,a)}),(a,b)$ 的所有线性组合即可。

直接 bfs ，由于最终只有 $O(n)$ 对，答案是 $O(n)$ 的。

神仙场。

A Number

原题链接

对每个数码分开考虑。对于一个数码来说，我们其实需要求的是一个最小的数 $i$ 使得

$\sum_{j \le i} (d - S(j,d)) < 0$

最后对每个数码的答案取最小值即可。

我们考虑这个东西怎么求。这个东西本身不太具有二分性，但是我们考虑对 $1 \sim 10^i - 1$ 求出这个前缀中的最小的前缀和以及整个的前缀和即可。然后我们就可以从高位到低位填数，从 $0$ 到 $9$ 枚举这位的数码，然后看看如果填入这个数后低位的最小前缀和会不会导致整个的最小前缀和 $<0$ ，即拿最小前缀和和前面的所有前缀和合并一下。

现在问题就是怎么确定位数了。如果实现了刚刚说的东西，直接从低到高位枚举位数，用之前求的那个东西看看是否仍然合法即可。

那么考虑怎么对 $1 \sim 10^i-1$ 求出这个前缀中最小的前缀和以及整个的前缀和。具体来说，我们设 $dp[i][k][0/1]$ 表示当前已经填了前 $i$ 位，其中有 $k$ 个数码 $d$ ，下一位从 $0$ 还是从 $1$ 开始填，此时得到的最小前缀和以及整个的前缀和是多少。转移就枚举下一位填啥合并一下即可。

这题需要高精，但是可以发现答案大小不超过 $10^{10a}$ ，即 $10^{160}$ 。所以直接上高精即可。

复杂度大概是 $O(l^3d^5)$ ，高精常数很小。

三道 Petrozavodsk 和 Open Cup

Different Summands Counng

链接

反套路题。介绍一下 $O(m^3\log n)$ 的卡常做法和 $O(m^3)$ 的标算。

我们考虑对于一个数，算出它恰好没有出现过的方案数，然后用总方案减去这个就是出现过的方案数量。前面这个可以方便地容斥成钦定，而如果是钦定且这题是有序拆分就可以用插板来安排剩下的数。

$\sum_{a=1}^n\left(\binom{n-1}{m-1} - \sum_{k = 0}^{\min(m,n / x)} (-1)^k \binom{m}{k} \binom{n-ka-1}{m-k-1}\right)\\ = \sum_{a=1}^n\left(\sum_{k = 1}^{\min(m,n / x)} (-1)^{k+1} \binom{m}{k} \binom{n-ka-1}{m-k-1}\right)\\ = \sum_{k = 1}^{m}(-1)^{k+1} \binom{m}{k} \sum_{a=1}^{n/m}\binom{n-ka-1}{m-k-1}\\$

这个东西看起来比较难算。我们考虑第一层直接枚举，怎么计算后面这个东西。

A

求出 $n$ 个数都是不到 $m$ 质数，且 Nim 游戏后手必胜的方案数。

$n \le 10^9,m\le 10^6$ 给定模数。

考虑到质数没啥好的性质，看起来也只能够去算这个异或卷积 $n$ 次方。

但是直接写完发现这东西巨慢无比。考虑怎么优化常数。

可以发现最后只需要求 $A[0]$ ，这个数在异或卷积式子可以看出为所有数的和，而 $\text{IFWT}$ 在异或卷积其实就是做一次 $\text{FWT}$ 然后每个数除以 $len$ 。因此我们最后没必要做一次 $\text{IFWT}$ ，直接求所有数的和除以 $len$ 即可。

然后会发现由于模数不固定每个数做一次 $n$ 次幂巨慢无比。但是做一次 $\text{FWT}$ 后每个数的绝对值不会超过之前所有数的和，而之前所有数的和，即质数个数，是 $O(\frac n{\ln n})$ 级别的，对 $1 \sim 2.5\times 10^5$ 预处理 $n$ 次方即可。这样就可以跑得很快了！

D1T1 D2T1 非常签到，就不写了。

不会真的有人写 D1T3 吧，不会吧不会吧

D1T2

首先考虑部分分，部分分就是直接求 $\max[l,l+c]$ 为初始值走 $[l+c,r+c]$ 的单调栈的长度。

我们考虑设数组 $b_i$ 表示在经历若干操作后， $A_i$ 的值变成了原序列中 $[i,b_i]$ 的最大值。

考虑 $b_i$ 的转移，不难发现就是一次区间平移然后往最后插入一个 $b_r$ 。

但是即使维护了 $b_i$ 仍然不好方便地做这个东西。然后就有一个非常神仙的转化：设 $c_i = \max[b_{i-1}+1,b_i]$ ，也就是把相邻两个 $b_i$ 之间的东西作为 $c_i$ ，特别的，如果 $b_{i-1}=b_i$ 我们认为 $c_i = 0$ 。这样转化后，会发现答案就类似于之前部分分的东西，是 $[l,b_l]$ 之内的最大值在走 $c[l,r]$ 的单调栈长度。画图一下就会发现这个转化非常有道理，就是把重复部分去掉了。

考虑怎么维护 $c$ ，不难发现对 $b$ 的操作对应到 $c$ 就是将 $c_l,c_{l+1}$ 中保留较大的值，然后在 $c_r$ 处插入一个 $0$ 。而插入 $0$ 其实是不存在的操作，所以实际上只需要支持删除即可！

但是还是需要维护 $c_i$ 实际上对应的是 $A$ 中的哪个数，这里还是得平衡树的（）后面直接楼房重建的线段树即可。

复杂度 $O(n\log^2 n)$ 。

T1 NEERC2016 Cactus Construction

考虑一棵树怎么做。容易想到，我们保证递归完一棵子树得时候根为 $2$ ，其他内容为 $3$ ，然后当前点 $u$ 设 $1$ ，于是每次就连 $1 \to 2$ 然后把 $2$ 整成 $3$ ，再做下一棵子树即可。这样只需要三种颜色。

考虑仙人掌咋办。还是类似地，我们尝试做完一个环的时候把最上面设置成 $2$ ，这里为了方便，可以类似圆方树把一条边也看成长度为 $2$ 的环。然后考虑类似建立圆方树的过程。如果一个儿子 $v$ 自己为一个环顶（也就是 low[v] == dfn[u]） ，我们来处理这个环。按照弹栈顺序（也就是从深到浅）来做。我们把起始点设置为最深的，为了方便最后连完环上最后一条边把它设置成 $4$ ，然后考虑下一个点，类似树，钦定做完这个子树的时候它的颜色是 $2$ ，子树其他点是 $3$ ，然后把 $2,4$ 连起来，然后把 $2$ 设成 $1$ ，再考虑下一个点的时候就 $2,1$ 连边，然后把 $1$ 变成 $3$ ，把 $2$ 变成 $1$ ，一直这么做即可。最后把 $4,2$ 连起来即可。

可能需要判长度为 $2$ 的环，我的代码多进行了几次无用操作就不需要了，但是操作数略高。

终于做了一些比 入门篇 难一些的题。

A AUOJ1600 礼物

其实是道板子+式子题。大概是 Burnside 引理的第一种题型（强行拼上去）。

我们考虑设 $f(a,b)$ 为 $a$ 个点形成环，从中选择 $b$ 个位置选中，且选中位置没有连续 $k$ 个的方案数量。

由于是循环同构，我们枚举置换再算环的个数，然后就可以得到和入门篇基本一样的式子，然后最后就是：

$\sum_{i | n,i | m} f(\frac n i ,\frac m i) \varphi(i)$

考虑怎么快速计算 $f(a,b)$ 。

B Parades

这题有一个关键的性质：可以发现一定有一种全局最优解满足每个点都是局部最优解。具体来说，由于每个点向上只有一条边，所以即使你在这个点子树的时候放弃选择一条路径，也只能最多获得 $1$ 的贡献，还不如直接选择子树之内。（感觉这种性质在权值全 $1$ 的时候都可以尝试一下有没有）

于是我们设 $dp[u]$ 表示 $u$ 子树最多可以选多少个路径，再对每个子树维护出一个集合，这个集合中的点满足存在一个选择最多路径的方案，使得这个点没有被覆盖。

考虑转移，由于 $n \le 10^3$ 且度数很小，我们可以在每个点做一个状压，转移出当连向某些儿子的边被选择时，最多可以选择多少个路径（感觉可能这个东西也是可以流的）。然后把所有取到最大值的状态取个交，得到的集合就是如果想要获得最大值就必须放弃的子树，剩下的子树都是存在方案使得不被覆盖的，由于最多只会选一条路径连上去，所以这么做是对的。

复杂度 $O(\frac{n^2}{\omega} + nd^22^d)$ 。

A (False) faces

题解在 这里 。

B Pachinko

我们考虑设出 $s_{i,j}$ 表示经过 $s_{i,j}$ 的期望次数。那么可以对每个格子列出一个方程。由于每个 T 位置不会往外走，也就是说走到这个点就结束了，所以期望次数可以直接看成一个概率，最后除以会结束的总概率即可。但是直接进行高斯消元是 $O(n^3m^3)$ 的，无法接受。

然后会发现这个矩阵非常有性质。由于这个矩阵是 $n \times m,10^4 \times 20$ 的，而一个位置的方程仅在 $[i-m,i+m]$ 有值。因此高斯消元的时候，每一行只会影响到后面 $m$ 行。

但是还有一个问题，在进行交换的时候，显然只需要尝试把后 $m$ 行交换过来，交换过来后就可能影响 $[i+1,i+2m]$ 的系数了。因此需要对每个位置存储 $[i-m,i+2m]$ 的系数。记得在交换后需要改变这个方程可能有值的区间，由于 $i$ 前面都是 $0$ ，这个改变只可能是前面砍掉一些 $0$ 后面加上一些 $0$ 。

复杂度 $O(nm^3)$ 。

A Yet Another LCP Problem

考虑反过来看串，如果建立前缀树，会发现这个 LCP 长度的问题就可以看成对于所有一类集合的点都到根全部 +1 ，对所有二类集合点求和。但是由于一般来说前缀树显然是建不出来的只能建出 parent 树，而如果建出 parent 树后，相当于这个点父亲到根的所有串全部 +1 ，然后需要特殊处理当前点。因此树剖显得挺难受，于是考虑建立虚树后 dfs 两遍做即可。细节可以参考代码。

复杂度 $O(n\log n)$ 对每个点上串的长度需要排序，以及建虚树时需要排序。

Light switches

注意到 $S \le 30$ ，我们考虑进行折半搜索。考虑复杂度是啥，如果所有集合操作都使用 bitset ，不难发现这里的两个开关并起来就是做个异或，那么考虑枚举一下前 $A$ 个开关的情况进行预处理，然后查询的时候对剩下的开关枚举情况，预处理的东西丢进一个 unordered_map 里（貌似 unordered_map 对 bitset 有自带的 Hash 方式），复杂度就是 $O(2^A \frac Nw + q\frac N w 2^{S-A})$ ，不难发现在 $A$ 大概取到 $20$ 的时候，运算次数大概是 $\frac{10^9}{32}$ 左右，非常稳。

一个我没写过的套路。

这个题目其实就是问你给你一个串，可以往前添加一些字符，往后添加一些字符，有多少种添加方式使得最终串不同。

我们先考虑向前添加字符，不难发现一个字符串向前添加字符可以得到的就是 parent 树子树内的本质不同的所有字符串。设这个串长为 $|S|$ ，子树内的本质不同串的个数为 $a$ ，当前点上最短串长为 $b$ ，那么添加方案数就是 $a+b-|S|$ 。

我们按照与对角线平行的线上的数来考虑。如果只考虑在一条这样的对角线上进行操作，那么就变成了一个普通的 Nim 游戏。而如果有很多对角线，不难发现在进行一次操作的时候，这个人可以把后面的所有对角线的状态改变。

于是我们考虑找出第一个异或和不为 $0$ 的对角线，这个对角线单看是先手必胜的。考虑先手对这个对角线进行一次操作把它的异或值变为 $0$ 。要么此时已经没有数了，先手胜利。要么后手会有一些选项：选择这条对角线或之前的对角线，这样的话必然会导致一条对角线的异或和变成非 $0$ ，先手可以继续操作。否则他会去选择这条对角线后面的对角线。但是后面的对角线可以由先手这一轮操作一下，使得后面的所有对角线的异或和都为 $0$ ，于是后手就没办法了。

于是就可以得出结论：后手必胜当且仅当所有对角线的异或和为 $0$ 。

首先，模 $2$ 就是行列式的值。

我们考虑容斥，钦定某些列没有数被选，那么有

$\text{perm } A = (-1)^n \sum_{x \in \{0,1\}^n} (-1)^{x_1+x_2+\cdots +x_n} \prod _{i=1}^n (Ax)_i$

也就是钦定某些列不选，然后每一行任意选一个数。

由于后面有一个 $\prod$ ，也就是说一个 $x$ 会造成贡献当且仅当 $Ax$ 中 $0$ 的个数小于等于 $1$ 。

A Winding polygonal line

神仙构造。

考虑拿凸包上一个点 $A$ ，然后每次找一个点 $B$ ，如果是 L ，则使得剩下的所有点都在 $AB$ 的左侧，然后连过去即可，否则就使得所有点都在 $AB$ 右侧。不难发现这样每一轮都一定能找到剩余点继续，且由于所有点都在一侧，显然不可能出现线段相交。

复杂度 $O(n^2)$ 。

B Distinctification

考虑给定一段序列怎么算出答案。不难发现对于一个 $A_i$ ，我们一定会找到一个最大的 $k$ 满足 $[A_i,A_i+k-1]$ 的数的个数正好是 $k$ ，然后把这些数进行操作使得这些数互不相同。

我们定义一个方案的权值为 $\sum_i A_iB_i$ ，那么最终需要花费的代价是 $W_e - W_s$ ，而我们希望这个代价尽量小，也就是最小化最终状态的代价。而且不难发现，在题目的条件下，一定可以将 $A_i,B_i$ 变成 $k,B_i$ 其中 $k \in [A_i,A_i+k-1]$ 。具体为啥想一想就会发现这个方案非常容易构造，可以先任意得到一个每个数不同的方案，然后一个一个归位即可。

考虑对于一个数组 $a_{1,\dots ,n}$ 怎么求出答案，其中 $0$ 为根。考虑每一条边 $i \to f_i$ 的贡献，显然是 $siz_i(n+1-siz_i)$ 。那么我们可以枚举这个点的子树的 $siz$ 然后算这种情况的概率，而算概率则直接统计有多少种加边后的方案使得取到这个 $siz$ 然后除以总方案数 $n!$ 即可。考虑方案数量的计算，如果确定后面有 $s$ 个点在子树内（不包括 $i$ ），这些点的父亲的方案分别是 $1,2,3,\dots ,s$ ，因为第一个子树内的点的父亲必须是 $i$ ，第二个可以是第一个或者 $i$ …… 然后考虑这个子树之外（不包括 $i$ ）的点。这些点的方案数显然依次是 $1,2,\dots,n-s-1$ 。最后考虑 $i$ 的父亲的方案数，它可以连向 $0 \sim i-1$ ，是 $i$ ，于是式子就是：

$\frac{1}{n!}\sum_{i=1}^n A_i \sum_{s=0}^{n-i} \binom {n-i} s s!(n-s-1)!i[(s+1)(n+1)-(s+1)^2]$

为了方便，暂时不写最前面的 $\frac 1{n!}$ 了。