Atcoder练习

Published: by Creative Commons Licence

  • Tags:

ThREE *

题意

https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_c

题解

比赛的时候没想到怎么做。比较偏数值技巧的题目。

由于树是二分图，将顶点分成两类，记作$L$和$R$，我们恒认为$L$中包含较少的顶点。

现在考虑两种情况：

  • 如果$\mid L\mid \leq \lfloor \frac{n}{3} \rfloor$，那么就讲$L$中的顶点全部用$3$的倍数来填充。
  • 否则，将$3k+1$全部用于填充$L$，而$3k+2$全部用于填充$R$，剩余的随意。

Manga Market *

题意

https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_d

题解

比赛的时候没做出来，昨天比赛也出现了一道指数性增长的DP，也没发现，看来需要多多练习这类指数增长的DP了。

这个问题可以很容易推出DP公式，其中$dp(i,j)$表示的是仅考虑前$i$个商店，共遍历了$j$个商店的最少花费时间。

很容易发现DP的时间复杂度是$O(n^2)$，是过不了的。

但是由于题目里面暗藏了一个线索，每个商店的等待时间是$at+b$，其中$t$是到达时间。这里我们将商店分成两类，第一类就是$a$为0的商店，第二类就是$a$不为0的商店。第一类肯定放在第二类之后决策，这时候贪心即可。现在考虑第二类的商店，在我们访问了一家店铺后，离开时间至少为$1$，可以发现在第二家商铺的时候，第一家商铺花费的时间会在结果出现两次，而第三家商铺的时候，第一家商铺花费的时间会在结果中出现四次。实际上这是一个指数增长的过程，因此我们可以断定最多访问$\log_2T$家第二类商铺。这样DP就可行了，总的时间复杂度为$O(n(\log_2T+\log_2n))$。

Square Rotation *

题意

https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_d

题解

首先如果两个顶点坐标模$d$的时候相等，那么我们可以旋转操作将这些坐标任意排放。现在的问题是有$x_{ij}$个顶点位于坐标$(i,j)$处，问至少需要多大的方形可以包括所有顶点。

考虑大小为$ad+b$的情况，这时候若$i,j<b$，那么最多允许存在$(a+1)^2$个顶点，如果$i,j\geq b$，那么最多允许存在$a^2$个顶点，其它情况最多允许存在$a(a+1)$个顶点。

我们可以用二分法来查找最小的方形大小。同时利用区间和技术来判断左下角为$(x,y)$的时候矩形是否满足条件。总的时间复杂度为$O(D^2\log_2(nD))$。

Atcoder jsc2019_qual_d

题意

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d

题解

一个图，如果所有的环都是偶数长度当且仅当该图是二分图。

首先说方案，对于n，我们将其分为n层。如果两个顶点的标号i、j第一个不同的二进制位为第k位，那么边(i,j)属于第k类。由于第k个图中的边的两侧端点的第k二进制位都不同，因此一定是二分图。由此证明了方案是正确的划分。

下面证明最少要划分为 \(\lceil \log_2n \rceil\) 层。

一个图能的边如果能够被分类为k类，那么我们称该图满足k分，满足k分的显然也能满足k+1分。下面我们证明一个命题：

命题：能被k分的最大完全图包含$2^k$个顶点。

证明：

归纳法证明。当k为0和1的时候命题显然成立。下面考虑已知命题在$k=x$时成立，那么考虑大小为$2^x+1$的完全图。我们知道它至少得被x分，那么它能被x分吗？假设它能被x分，我们知道每个层级都是将图划分为左右两部分，图中共$2^x+1$个顶点，因此任意层的二分图的至少一侧有$2^{x-1}+1$个顶点。考虑我们第x层二分图，我们设左边有不少于$2^{x-1}+1$个顶点，那么我们将左边的顶点重新标号为$1,2,\ldots, 2^{x-1}+1$，接下来将其余所有顶点删除，这就转换成了大小为$2^{x-1}+1$的图的一个分类。考虑到第x层图只有左侧顶点，即没有边的存在，因此不需要第x层图。即我们证明了大小为$2^{x-1}+1$的图能被$x-1$分。但是由归纳法知道，这是不可能的。

至此，命题证明完毕。

Atcoder AGC001C

题意

https://atcoder.jp/contests/agc001/tasks/agc001_c

给定一颗树，删除最少的顶点，保证剩余顶点组成一颗直径不超过k的树的前提下，要求树尽可能大。

题解

先学习了一下树的中点和中边的概念。

如果原树半径就小于等于k，那么结果就是原树。

否则，那么结果的半径一定是k。如果k是偶数，那么可以寻找结果的中点，如果找到，那么结果一定是距离中点小于k/2的顶点集合（很显然这是一个满足条件的树，并且结果是这类树构成集合的一个元素）。

如果k是奇数，那么对应的求结果中的中边即可。

时间复杂度为$O(n^2)$。

ABC141F

题意

https://atcoder.jp/contests/abc141/tasks/abc141_f

题解

位运算典型问题第7题。

AGC015D

题意

https://atcoder.jp/contests/agc015/tasks/agc015_d

题解

问题问有多少个数可以通过$[A,B]$中的一个或多个数二进制或运算得到。

首先，很显然，区间$[A,B]$中的数肯定都能得到的。

这样我们手动排除一种特殊情况，$A=B$的情况，这时候结果一定为1。之后仅考虑$A<B$的情况。

接下来以二进制的视角观察数值。我们可以无视$A$和$B$的公共二进制前缀，因为这是一定会出现在或运算结果中的。这样我们可以认为$A$和$B$的最开头的二进制位不同，$B$的为1，$A$的为0。记此时$B$的有效长度为$L$。

接下来我们可以将区间$[A,B]$进行拆解，拆解为两部分$[A,2^L-1]$，以及$[2^L,B]$。

先看第二部分，假设$B-2^L$的有效长度为$K$，那么区间$[2^L,B]$可以生成$2^K$个不同的值。

现在考虑$[A,2^L-1]$，由于任意两个数或运算的结果一定不会小于任意一个操作数，因此可以直接断定$[A,2^L-1]$最多生成$2^L-A$个不同的数。

现在考虑两个不同的区间合作可以生成多少个不同的数值。事实上，可以分两种情况考虑，如果$2^K\geq A$，那么我们可以生成额外的$2^L-2^K$个数值。而在$2^K<A$的情况下，实际上我们要考虑的是从区间$[A,2^L-1]$和$[2^L,2^L+2^K-1]$中各取一个数进行或运算，我们提到过，任意两个数位运算或运算结果不会小于任意一个操作数，因此我们可以得到的数一定处于区间$[2^L+A,2^{L+1}-1]$中，总共$2^L-A$个。

ARC066B

题意

https://atcoder.jp/contests/arc066/tasks/arc066_b

题解

首先我们需要意识到 \(a+b=a \oplus b +2\cdot(a\& b)\) 。

对于只有a为1，而b为0的二进制位，我们可以该二进制位改为a为0，b为1，这样做，$a\oplus b$和$a+b$都不会发生改变。因此处理过后的a是b的一个二进制子集。

现在我们仅考虑符合上面性质的a、b对（a是b的二进制子集），如果有

\[a\oplus b= u =c\oplus d\\ a+b=v=c+d\Rightarrow a\&b=c\&d\]

那么我们可以发现对于u中出现的二进制1，b和d都是1，而a和c都是0。而对于u中出现的二进制0，由第二个式子知道，b和d拥有相同的值。故a和c也拥有相同的值。

这样我们就证明了符合条件的(a,b)和(u,v)一一对应。要统计所有的(u,v)，可以通过统计(a,b)得到。

这边可以通过数位DP求解。

ARC067F

题意

https://atcoder.jp/contests/arc067/tasks/arc067_d

题解

考虑对于$B_{ij}$，记$x$为满足$B_{xj}>B_{ij}\land x < i$条件的最大值，记$y$为满足$B_{yj}>B_{ij}\land y>i$条件的最小值。

这意味着所有在区间$(x,y)$中游历并经过$i$的旅途，第j张票一定是在餐厅i消费的。对于所有这类旅途，我们在平面上绘制两个顶点(i,i)和(x+1,y-1)，由这两个顶点所确定的矩形中的所有顶点(a,b)，其对应的旅途为从第a个餐厅走到第b个餐厅，此时很显然会穿过餐厅i，且不会到达餐厅x和餐厅y。因此我们需要给其打上标记。

上面的过程可以用矩阵上打差分标记实现。在使用矩阵之前将所有惰性标记下推。之后遍历所有的$n^2$种旅途，暴力枚举每一种旅途的收益即可。

总的时间复杂度为$O(n^2+nm)$。

ARC068E

题意

https://atcoder.jp/contests/arc068/tasks/arc068_c

题解

这道题必须注意到一个非常关键的东西，不然时做不出来的。

先考虑现在处理移动距离为d，考虑一个区间[l,r]，区间的大小为r-l+1，如果区间的大小大于等于d，那么这个区间一定会覆盖到这次旅途中的某个城市。如果区间的大小小于d，我们可以直接记录在数组中，之后暴力寻找0,d,2d…这些下标的值统计，可以发现区间不会被重复统计（即最多在该区间停留一次）。

之后就是随便写写了，时间复杂度为\(O(m(log_2m)^2+n\log_2n)\)。

ABC138F

题意

https://atcoder.jp/contests/abc138/tasks/abc138_f

题解

简单分析可知，对于所有满足条件的(x,y)对，y和x共享最高二进制位，且(x&y)=y。

我们可以用动态规划来求解，按照是否处理了首位二进制，是否严格上界，是否严格下界，共8种状态。

Atcoder AGC036D

题意

https://atcoder.jp/contests/agc036/tasks/agc036_d

题解

想肯定是想不到的，看的题解。

我们从第0个点开始找单源最短路径，在无负环的情况下，最短路径是存在的。我们定义$p_i$为到顶点i的最远路径。由于存在权重为0的i到i+1的路径，因此可以断定$p_i$是单调递减的，即 \(p_0\geq p_1 \geq\ldots \geq p_{n-1}\) ，从而我们可以定义一组非负整数$q_i$，使得$q_i=p_i-p_{i-1}$。

考虑一条权重为-1的边，假设起点为i，终点为j。那么这条边在最短路中的含义是

\[p_j\leq p_i-1\Rightarrow p_i-p_j\geq1\Rightarrow q_i+q_{i+1}+\ldots + q_{j-1}\geq 1\]

考虑一条权重为1的边，假设启动为j，终点为1，那么这条边在最短路中的含义是

\[p_i\leq p_j+1\Rightarrow p_i-p_j\leq 1\Rightarrow q_i+q_{i+1}+\ldots + q_{j-1}\leq 1\]

我们的目标实际上是为非负整数$q_i$赋值，使得违背的约束的总费用最小。可以容易得出，当我们为$q_i$赋值大于1的整数时，我们将其改成1，不会有新的约束被违背，因此我们可以断言在最终结果中$q_i$只能为0或1。

之后就是动态规划了，记$f(i,j)$表示为$0,1,\ldots,j-1$，并处理完所有右边界小于j的约束后所需要支付的最少费用。

对于转移$f(i,j)$到$f(j,x)$，我们需要支付所有新违背的约束的费用，我们会违背以下符合条件的约束：

\[\sum_{a=i+1}^{x-1}\sum_{b=i+1}^{x-1}[a\leq b]cost(a,b)\]

以及

\[\sum_{a=0}^j\sum_{b=i}^{x-1}[a\leq b]cost(b,a)\]

其中 \([a\leq b]cost(a,b)\) 表示的是形如 \(p_a+_\ldots+p_b\geq1\) 的约束，而 \([a\leq b]cost(b,a)\) 是形如 \(p_a+_\ldots+p_b\geq1\) 的约束。而这两部分内容实际上是子矩阵和问题，我们可以预先处理前缀之后利用差分得到。总的时间复杂度为$O(n^3)$，考虑到$n\leq 500$，这个方法是可行的。

Atcoder ARC058C

题意

https://atcoder.jp/contests/arc058/tasks/arc058_c

题解

简单的数论貌似很难处理，首先将包含问题变成不包含问题。但是可以用一些特殊的方式解决。

我们可以将数值序列看作一个字符串序列，这样问题就变成了统计包含某个特定连续子序列的字符串。

由于X、Y、Z都很小，我们可以暴力枚举所有可能的子序列（可以切分为三部分，第一部分的总和为X、第二部分为Y、第三部分为Z）。这样的序列总数不会超过一万个。

之后我们建立一个AC自动机，将可能的子序列全部插入到里面，之后AC自动机种的每个状态都对应一个动态规划状态，最终的状态最多只有3万多个。

之后我们建立递推公式，记$f(i,s)$表示考虑设置完前i个数值后，处于状态s的方案数，之后利用AC自动机递推就可以了。

大概的时间复杂度为$O(10^5n)$。

统计包含某个子序列的所有序列数问题的一般做法如下：

  1. 由于包含问题容易重复统计，因此需要先转换为不包含问题。
  2. 之后将禁止出现的子序列插入到AC自动机种。
  3. 将AC自动机中的每个顶点作为DP状态，之后进行递推即可。

Atcoder AGC002F

题意

https://atcoder.jp/contests/agc002/tasks/agc002_f

题解

当k=1时，答案很显然时1，考虑非1的情况。

放球问题，一般都可以通过下面的动态规划解决。

我们定义dp(i,j)表示放置i种颜色的球（每种颜色k-1个），以及j个0颜色球，有多少种方案。可以推出：

\[dp(i,j)=dp(i,j-1)+dp(i-1,j)\cdot j \cdot {i(k-1)+j-1\choose k-2}\]

这里的解释是，放置的第一个球或许是0颜色球，或许是其他i种颜色里的一种。如果是i种颜色种的一种，那么剩下的同颜色的$k-2$个球可以通过组合数学与后面的i-1种颜色及j个0颜色球合并。

大抵上，一般如果球之间有依赖关系。即球之间的关系存在拓扑关系，那么就可以用类似的动态规划得到。$dp(i_1, i_2, \ldots)$表示第$j$类球有$i_j$个。

Atcoder AGC004E

题意

https://atcoder.jp/contests/agc004/tasks/agc004_e

题解

用动态规划解决，定义$f(l,r,u,d)$表示我们抵达的最靠左的位置的列号与出口的列号差值为l，最靠右的位置的列号与出口的列号的差值为r，最靠上的位置的行号与出口的行号差值为u，最靠下的位置的行号与出口的行号差值为d。

ARC066C

题意

https://atcoder.jp/contests/arc066/tasks/arc066_c

题解

很容易想到$O(n^2)$的区间DP解法。下面我们来证明最优解可以通过最多嵌套两层括号得到。

首先很容易发现下面几个性质：

  • 左括号一定出现在负号后才有意义
  • 左括号不会连续出现（即不存在((的情况）
  • 对于嵌套奇数层的情况下，右括号出现的位置的前一个运算符一定是负号。
  • 对于嵌套偶数层的情况下，右括号出现的位置的前一个运算符一定是正号。

下面考虑6个整数： \(a<b<c<d<e<f\) ，假设a、b、c表示左括号出现的位置，d、e、f表示右括号出现的位置。这是典型的三层括号嵌套的情况。

我们可以将括号转换为：a、b、d为左括号，c、e、f为右括号，此时只嵌套两层，且运算结果不变。

因此我们怎么了括号最多嵌套两层。这时候我们定义 \(dp(i,j)\) 表示在处理完前i个数后，还有j个左括号未匹配的情况下可以可以得到的最大值。其中j仅可能为0、1、2。

总的时间复杂度为$O(n)$。

AGC032D Rotation Sort

题意

https://atcoder.jp/contests/agc032/tasks/agc032_d

题解

首先左旋和右旋可以理解为将一个数值前移和后移。

之后我们可以建立一个DP公式，记$f(i,j)$表示将前i个数按大小排序，且最大的k个数经历了后移过程。

那么考虑一个状态$f(i,j)$以及它的转移。考虑数$a_{i+1}$，假设$a_1,a_2,\ldots,a_i$中有$r$个数比它大，那么要将前$i+1$个数安排成有序，我们需要要么将$a_{i+1}$进行一次左移，此时对应的转移目标为$f(i+1,min(r,j))$；或者$a_{i+1}$不动，而比它大的$r$个数右移，这种情况的转移目标$f(i+1,r)$，前提条件是$j\geq r$；或者让$a_{i+1}$也右移，这时候的转移目标为$f(i+1,j+1)$，前提条件是$j\geq r$。

这样我们只需要$O(n^2)$的时间和空间复杂度就可以解决整个问题了。

ARC073D

题意

https://atcoder.jp/contests/arc073/tasks/arc073_d

题解

可以很简单地建立动态规划公式：dp[k][i][j]表示处理完k个请求后两个指针的位置分别为i、j的最小移动次数。

我们发现处理完第k个请求后其中一个指针一定是$x_k$，因此可以压缩一下动态规划dp[k][i]表示处理完k个请求后，一个指针为$x_k$，另外一个指针为i的最小移动次数。

处理第k个请求的时候，有两种行为：

第一种，位置为$x_{k-1}$的指针移动到$x_k$处，此时，dp[k][i]=dp[k-1][i]+abs(x[k]-x[k-1])。

第二种，从位置不为$x_{k-1}$的指针移动到$x_k$处，此时，我们只需要特殊处理dp[k][x[k-1]]即可。

我们可以维护一株线段树，在线段树上做转移即可。时间复杂度为$O(q\log_2n)$。

ARC078D

题意

https://arc078.contest.atcoder.jp/tasks/arc078_d

题解

定义cost(S,T)表示V的子集S和T，所有两端点分别处于S和T的边的权重之和。

定义dp(S,t)表示，包含顶点1的子集S，仅考虑S和{t}中的并集中的顶点，从顶点1到t存在唯一路径的最小成本。

之后考虑到最终结果中仅存在唯一的从1到n的路径，因此我们可以不断枚举路径上最后一个顶点，倒数第二个顶点，从而获得最小费用。

我的做法的时间复杂度是$O(3^nn^2)$，不太明白官方的$O(3^nn)$是怎么做大的。

ARC072E

题意

https://atcoder.jp/contests/arc072/tasks/arc072_c

题解

考虑修改$d_i$，假设此时我们的位置为$p_i$，那么我们可以通过修改距离使得之后的距离处于$0$到$p_i$之间。如果我们知道当处理第$d_{i+1}$时，存在某个距离x，当处于距离x时无法抵达终点。那么，这意味着假如我们在第i步结束时移动到x，那么最终就能不抵达终点。

注意这样的x可能会有很多，但是只需要维护最小的那个就可以了。

ARC076D

题意

https://arc076.contest.atcoder.jp/tasks/arc076_d?lang=en

题解

问题实际上就是前缀匹配问题形态3。

Atcoder Zabuton

题意

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_d

题解

前缀匹配问题形态4

Atcoder jsc2019_qual_c

题意

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c

题解

挺难的题。

首先我们注意到操作顺序不重要。

之后还需要注意到对于两次操作(l1,r1),(l2,r2)，等价于(l1,r2),(l2,r1)。

现在我们需要为每个操作分配一个L、R属性，分配到L的表示其作为操作左端点，R的表示作为操作右端点。

继续观察发现如果一个i位置为L，那么i和i-1在所有操作完成后具有不同的颜色（原本相同变作不同，原本不同变作相同）。如果位置j为R，那么j和j+1在所有操作完成后具有不同的颜色。当然如果两个相连的位置为RL，那么就会相互抵消，两者颜色保留。

通过上面观察我们找到了一个唯一分配L，R的方案，利用这个思路$O(n)$内可以分配LR。

之后为了统计操作数，我们首先要找出左右括号的配对可能数。之后结果还要乘上$n!$，作为操作执行顺序对结果的贡献。

Atcoder agc037_b

题意

https://atcoder.jp/contests/agc037/tasks/agc037_b

题解

感觉很神奇的题目。这个题目可以继续推广出去，但是解法是相同的。

我们先先考虑只有两种颜色时的情况。假设只有颜色为黑色和白色的两种颜色的球的长度为2n的排列，每个球赋予不同的权值。

我们将黑球的权值从小到大记作 \(B_1,B_2,\ldots,B_n\) ，之后将白球权值从小到大记作 \(b_1,b_2,\ldots,b_n\) 。现在记 \(m_i=\min\{B_i,b_i\}\) ，同时记 \(M_i=\max\{B_i,b_i\}\) 。记录$x_i$为实际与$B_i$配对的白球。

当我们分别将$b_i$和$B_i$进行配对时，得到了一个解： \(\sum_{i=1}^nM_i-m_i\) 。下面我们证明这就是最优解：

首先假设我们要构造一组分配 \((x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\) ，希望使得该公式最大： \(\sum_{i=1}^n\min\{x_i,y_i\}\) 。不妨认为$m_1=B_1$，那么与$B_1$配对的白球的最好的选择就是$b_1$（假设是其它的，我们可以用其于$b_1$交换，这样结果只大不小）。重复这个过程，我们发现正好满足： \(\min\{x_i,y_i\}=m_i\) 。同理我们可以证明要使得 \(\sum_{i=1}^n\min\{x_i,y_i\}\) 最小，只需要令 \(\max\{x_i,y_i\}=M_i\) 。因此对于任何的配对(x_i',y_i')，都有：

\[\sum_{i=1}^n|x_i'-y_i'|\geq \min_{x,y}\sum_{i=1}^n\max\{x_i,y_i\}-\max_{x,y}\sum_{i=1}^n\min\{x_i,y_i\}=\sum_{i=1}^nM_i-m_i\]

现在我们可以简单推广到任意多颜色的情况。假设有$m$种颜色，记第$i$种颜色第$j$次出现的下标为 \(I_{i,j}\) 。那么最小的配对差为：

\[\sum_{i=1}^n\max_k\{I_{k,i}\}-\min_k\{I_{k,i}\}\]

下面说一下怎么统计最小差的配对方案数目。将求球类为三类，若 \(I_{i,j}=m_i\) ，那么称$I_{i,j}$为第一类点，若 \(I_{i,j}=M_i\) ，那么称$I_{i,j}$为第二类点，否则称为第三类点。问题要求我们统计有多少种配对方案，对于一个配对$(a,b,c)$，要求三者颜色不同，且a是第一类点，c是第二类点，b是第三类点。

在这个问题场景中，我们会发现，只要三类点一出现就会和唯一颜色的一类点匹配，从而保证一类点颜色唯一。而三类点一出现，就必定和另外两个点匹配。因此可以贪心地从左往右扫描，记录r、g、b、rg、rb、bg的出现次数，每种可能都要乘到结果中去。最后结果还要乘上n!，表示匹配和人的关系。

Atcoder AGC003E

题意

https://atcoder.jp/contests/agc003/tasks/agc003_e

题解

首先如果对于连续的两次请求，后一次请求的$q_i$小于前面一次请求$q_{i-1}$，那么请求$q_{i-1}$不会对最终的统计带来任何影响，我们可以将其从请求队列中剔除。

因此最终保留下来的请求一定是一个严格递增序列，我们记作： \(q_1,q_2,\ldots,q_m\) 。

这个问题非常神奇的一点是我们可以反向统计。首先我们知道最终的请求$q_m$完成后序列的长度为$q_m$，我们维护一个数组$C$，$C_i$表示请求i完成后的结果序列对于最终结果的贡献。

算法流程如下：

当扫描第i个请求时，我们知道它的贡献为C_i，我们维护一个数h，它初始值为$q_i$，那么我们从$i-1$反向扫描所有请求，记扫描到第$j$个请求，如果$q_j\leq h$，那么就将C_j$增加 \(\lfloor h/q_j \rfloor C_i\) ，并将$h$减少为$h\pmod q_j$。重复这个流程。

最后如果$h$非0，那么我们可以建立另外一个数组$P$，其中$P_i$表示初始序列长度为$i$的前缀对最终结果的贡献。

重复这个流程，最终$i$在最终结果中出现的次数为 \(\sum_{k=i}^nP_i\) 。

由于$h$每一次改变，都会至少减少一半，因此可以推断出$h$最多改变$\log_2q_i$次，而且由于查询时严格增的，因此可以利用二分来查找下一个会使得$h$改变的请求，总的时间复杂度为 \(O(n\log_2n\log_210^{18})\) 。

AtCoder Grand Contest 037D

题意

https://atcoder.jp/contests/agc037/tasks/agc037_d

题解

为最终处于不同行的元素提供不同的颜色，相同行的元素相同的颜色。问题等价于，重排每一行，使得每一列的元素颜色不同。

我们建立一个n*n的二分图。

要处理n*m矩阵，每种颜色恰好出现m次。先考虑第一列，我们希望保证第一列中所有元素颜色不同。如果第i行包含颜色j，那么我们在二分图左边第i个顶点和右边第j个顶点之间连一条边。由霍尔定理知，二分图一定存在完美匹配。我们找到完美匹配，之后重排元素，并忽略第一列。之后我们需要处理n*(m-1)矩阵，每种颜色恰好出现m-1次，用同样的技术就可以处理。

Atcoder jsc2019_qual_e

题意

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e

题解

问题要求我们为每一行选取一个卡片，每一列选取一张卡片。下面我们建立一个二分图B，图B的左边顶点表示的是卡片，而右边则为每个行列均建立一个顶点。卡片与所在的行列连一条带权重的边。问题要我们找到最大权的匹配。

我们考虑结果，如果结果中包含卡片$(i,j,a)$，那么卡片要么与第i行连边，要么与第j行连边。我们重新建立一副图G，图中为每个行列建立一个顶点，如果卡片$(i,j,a)$被选择到结果中，那么就将第i行和第j列所代表的顶点加一条边。我们会发现结果是若干个连通分量，每个连通分量要么是树，要么是树上加一条边（只有一个环的连通图），因为一个连通分量m个顶点不能同时分配给m+1条边。

考虑权重最大的卡片$x=(i,j,a)$，容易得知x一定会出现在结果中（如果不出现，可以用x替换与其同行的出现在结果中的卡片），因此在G中行$i$和列$j$之间是始终存在一条边的，这意味着我们可以将二个顶点合并。之后问题的规模就被缩小了，重复这个流程直到所有卡片都被处理完了。

要维护G，用并查集就足够了，加上预先对边排序的时间复杂度，总的时间复杂度为$O(n\log_2n)$。

Atcoder codefestival_2016_final_e

题意

https://atcoder.jp/contests/cf16-final/tasks/codefestival_2016_final_e

题解

很好的题目。

首先我们发现我们吃饼干的次数k至多为$O(\log_2n)$级别，因此我们可以直接暴力枚举吃饼干的次数。

考虑次数为k的情况下，假设第$i$次吃饼干之前我们烤了$s_i$秒，而最后我们烤了$s_{k+1}$秒，那么我们花费的总时间为：

\[kA+(s_1+s_2+\ldots+s_k+s_{k+1})\]

同时我们必须满足最终得到饼干总数为n，我们可以将其描述为如下约束：

\[s_1\cdot s_2\cdot\cdots \cdot s_k\cdot s_{k+1}\geq m\]

这个问题实际上就是最小和最大乘积问题，我们可以将在$O(\log_2n)$的时间复杂度内求解，总的时间复杂度为$O((\log_2n)^2)$，非常的小。

ARC085E MUL

题意

https://atcoder.jp/contests/arc085/tasks/arc085_c

题解

最小闭合子图的模板题，记录一下。

ARC065E

题意

https://atcoder.jp/contests/arc065/tasks/arc065_c

题解

注意到是曼哈顿距离，因此我们可以将其转换为切比雪夫距离。

这样所有从顶点u可以到达的其它顶点都应该落在以u为中心边长为2*d(a,b)的正方形的边上。

剩下的就是一些平衡树的奇技淫巧了，在平衡树上维护每条与x轴平行的横线以及与y轴平行的竖线，总的时间复杂度为$O(n\log_2n)$。

ARC082C

题意

https://atcoder.jp/contests/arc082/tasks/arc082_c

题解

一开始想了个$O(n^4)$的DP解法，但是做到一半的时候越发觉得不对劲。

后来看了题解才知道自己漏了个非常重要的条件。

考虑一个可以构成凸包的点集合$S$，以及被$S$覆盖的点集$V$。$S$对结果的贡献应该为$2^{V-S}$。

考虑$V$的子集共有$2^V$种，其中共有$2^{V-S}$个子集是$S$的超集，而这些超集有一个公共点，就是从他们中生成的凸包的顶点集合一定是$S$。因此我们可以通过枚举有多少个集合生成的凸包的顶点集合一定是$S$，每个集合都对结果贡献1，来实现$S$对结果贡献相同的效果。

而每个子集只要面积非0，那么一定能生成一个合法的凸包，即对结果贡献1。因此我们可以通过计算所有面积非0的子集。我们可以先算出所有子集，之后减去面积为0的子集（空集、单个点以及共线点）。

AGC040C

题意

https://atcoder.jp/contests/agc040/tasks/agc040_c

题解

考虑一种放置方案，我们将所有奇数下标的A改成B、B改成A，那么现在不允许合并的就是AA和BB。

这样结果一下明显了起来，如果一种方案中A的数目或B的数目超过一半，那么一定不可消，否则一定可消。

因此问题实际上要我们统计的是有多少种方案，其中A不超过半数，B也不超过半数。

剩下的参考几类组合数加总的计算方式类型3即可。

Atcoder Balanced Piles

题意

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e

题解

记$f(i,j)$表示最大值为i时，且有j处堆积了i个方块的方案总数。

可以简单推出$f(i,j)=\sum_{t=1}^{d}\sum_{k=1}^nf(i-t,k)$。但是这里没有考虑相同数目方块之间的处理顺序，一种简单的技巧，就是我们重新定义$f(i,j)$，最大值为i时，且有j处堆积了i个方块，且我们已经确认了每个方块之间的处理顺序的方案总数。显然此时$f(0,n)$为$n!$。

修改了定义后，我们的递推公式也需要修改，新的递推公式为：$f(i,j)=j!\sum_{t=1}^{d}\sum_{k=1}^nf(i-t,k)$。

但是$O(n^2)$肯定过不去的，我们定义新的函数$g(i)$：最大值为i时，且我们已经确认了每个方块之间的处理顺序的方案总数。

这样新的递推公式即为$g(i)=\sum_{j=1}^nf(i,j)=\sum_{j=1}^nj!\sum_{t=1}^{d}\sum_{k=1}^nf(i-t,k)=(\sum_{j=1}^nj!)(\sum_{t=1}^{d}g(i-t))$。

上面的公式可以用前缀和线性处理。于是时间复杂度为$O(n)$。

Atcoder AtCoder Grand Contest 001E

题意

https://atcoder.jp/contests/agc001/tasks/agc001_e

题解

神题。

考虑i和j，对结果的贡献为 \(a_i+b_i+a_j+b_j\choose a_i+a_j\) 。其在组合数学上的含义为从点 \((-a_i,-b_i)\) 到 \((a_j,b_j)\) 的路径数，每一步只能沿着x正轴或y正轴方向移动单位1。

我们将所有点绘制再4000*4000的网格中，在这上面做DP就好了，最后统计需要去重。

Atcoder code festival 2016 qualc E

题意

https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_e

题解

设$P$表示所有$N$个元素的排列，而$P'$为指定了若干个元素后的排列集合。

那么要计算每个$P'$中元素的序号之和，等价于找到对于$P$中的每个元素，有多少个$P'$中元素大于等于它。

\[\sum_{s\in P'}\sum_{t\in P}[s\geq t]\\ =\sum_{s\in P'}\sum_{t\in P}[s = t] + \sum_{s\in P'}\sum_{t\in P}[s > t]\\ =|P'|+\sum_{s\in P'}\sum_{t\in P}[s > t]\]

注意到$s > t$，等价于存在下标$i$，满足对于任意$1\leq j < i$，都有$s_j = t_j$，且$s_i > t_i$。

因此我们枚举下标$i$，得出：

\[\sum_{s\in P'}\sum_{t\in P}[s > t]\\ =\sum_{i=1}^n\sum_{s\in P'}\sum_{t\in P}[s_1=t_1\land s_2=t_2\land \ldots \land s_{i-1}=t_{i-1}\land s_i>t_i]\\ =\sum_{i=1}^n\sum_{s\in P'}(s_i-1-\sum_{j=1}^{i-1}[s_i>s_j])\cdot (n-i)!\\ =\sum_{i=1}^n(n-i)!\sum_{s\in P'}(s_i-1-\sum_{j=1}^{i-1}[s_i>s_j])\\ =\sum_{i=1}^n(n-i)!\sum_{s\in P'}(s_i-1)-\sum_{i=1}^n(n-i)!\sum_{s\in P'}\sum_{j=1}^{i-1}[s_i>s_j]\]

上面这个式子可以利用BIT和一些枚举技巧就可以解决了，总的实际复杂度为$O(n\log_2n)$。

这个问题说明了一种计算在字典序上小于某个字符串的字符串数目的计算方法。

Atcoder jsc2019_qual_f

题意

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f

题解

毒瘤题。假设满足第一个条件的数目为$f(n,L,R)$，利用组合数学可以直接得到：

\[f(n,L,R)={n+R\choose R}-{n+L-1\choose L-1}\]

接下来考虑第二个条件，很讨厌的条件。会导致重复统计的问题。现在我们可以考虑在满足第一个条件的前提下，统计不满足第二个条件的方案数，之和通过总方案数减去不符合条件2的方案数得到符合条件2的方案数。

在不满足条件2的前提下，第M大的数和第M+1大的数不同。假设第M大的数为x，那么序列中包含M个大于等于x的数，和N-M个小于x的数，并且前者中至少包含一个x。

记录$g(x,y)$表示满足第一个条件的前提下，M个数大于等于x，而另外M-N个数小于y的方案数。那么我们之前要统计的结果就是$g(x,x)-g(x+1,x)$。

现在考虑如何统计$g(x,y)$，对于前M个数，由于都大于等于x，因此，我们可以将它们提前减去x，同时r和l减去xM。而后面的N-M个数，要小于y，这个是不好统计的，我们可以用容斥反过来处理。

由于随着x的增大，实际上容斥的过程会不断缩短（因为不可能同时有$r/x$个条件被满足)，简单计算就可以得出最终的时间复杂度为$O(n\log_2n)$。

ABC146E

题意

https://atcoder.jp/contests/abc146/tasks/abc146_e

题解

差点出车祸。一开始理解错误，后来发现是总和除去$k$，必须等于长度。

首先考虑一个简单版本，给定一个序列，问有多少个连续子序列，满足总和是$k$的倍数。这个应该很简单吧，维护前缀和，之后当考虑所有以$A_i$结尾的满足条件的子串，其数目等价于有多少前缀和，其对$k$取模等于$\sum_{j=1}^i A_i\pmod k$。这个用哈希表维护一下就好了。

之后考虑新的问题，不难发现所有满足条件的子序列长度一定小于$k$。我们可以将长度平摊给每个数字，即令$B_i=A_i-1$，那么我们在$B_i$序列上解决这个问题的简单版本即可。

下面证明这是正确的，实际上原来问题的每一个满足条件的$A$的子序列，设其总和为$a$，长度为$b$，由于$(a\%k)-b=0$，因此有$(a-b)\%k=0$，即对应一个$B$中的子序列。同理对于$B$中的一个子序列，由于$(a-b)\%k=0$，故一定可以推出$a\%k-b=0$。

Atcoder Beginer Contest 147F

题意

https://atcoder.jp/contests/abc147/tasks/abc147_f

题解

问题实际问的是对于所有子集的和，里面有多少不同的值。

首先令$Y=X-D$，那么$A_i=Y+iD$。可以将$Y$和$D$除去它们的最大公约数，接下来假设二者互质。

遍历我们可以取多少个元素，从0到n。假设现在遍历到k了。

我们可以将所有大小为k的子集的和称为第$k\pmod D$类。可以发现只有同类的和可能重复。

现在我们可以单独处理每类和。我们发现第i类和的公式为$(i+tD)Y+?D$。因此当我们将它们都减去$iY$后，所有和都是$D$的倍数。

考虑所有大小为k的子集的和，其中所有可能的值为 \(\{kY+vD|v\in [1+\ldots+k, (n-k+1)+\ldots +n]\}\)

因此删除$(k\pmod D)Y$后，再除去$D$，那么这些和就对应一个连续区间$[l,r]$。我们可以用平衡树维护。

ARC080F

题意

https://arc080.contest.atcoder.jp/tasks/arc080_d

题解

我们定义数值$p_i$表示第i个数是否与前一个数相同，相同则置0，不同则置1。当我们翻转区间$[l,r)$的时候，实际上是翻转$p_l$和$p_r$。

我们所需要做的就是把所有的$p_i$设置为0。

接下来我们仅考虑值为1处的位置。考虑i和j，如果i和j之间的距离$|j-i|$是素数，那么同时翻转i与j的操作次数为1，否则如果二者距离为偶数，由于任意偶数可以表示为两个素数的差，因此同时翻转它们所需要的操作次数为2。否则如果二者的距离为奇数，同时翻转它们所需要的操作次数为3（可以通过三个素数的加减得到任意奇数）。

之后我们贪心地尽可能多选择距离为素数的对匹配，之后选择位置奇偶性相同的对匹配，最后才选择位置奇偶性不同的对匹配。

选择距离为素数的对的最大匹配，可以用二分图，二分图的左边控制所有位置为奇数的点，右边控制所有位置为偶数的点。之后找到最大匹配k即可。

记有a个位置为奇数的点，b个位置为偶数的点，则最终结果为：

\[k+(\lfloor (a-k)/2 \rfloor + \lfloor (b-k)/2 \rfloor) \cdot 2 + (a-k-\lfloor(a-k)/2\rfloor) \cdot 3\]

AGC006C

题意

https://atcoder.jp/contests/agc006/tasks/agc006_c

题解

考虑$a_i$发生变化，容易推出发生变化后的期望值为： \(E[a_i']=E[a_{i+1}]+E[a_{i-1}]-E[a_i]\) 。

之后我们来理解形如 \(b'=a+c-b\) 等式的几何含义。

考虑一个数轴，我们在$a$、$b$、$c$、$b'$处各放了一个顶点，记作$A$，$B$，$C$，$B'$。

可以发现： \(b'-a=c-b\\ c-b'=b-a\)

这意味着操作$a_i$会导致$a_i$到$a_{i-1}$以及$a_{i+1}$到$a_i$的距离交换了。

因此假如我们维护的不是每个顶点的具体位置，而是形如$d_i=a_i-a_{i-1}$的差量，那么一次变换可以简单的表示为 \(swap(d_i,d_{i+1})\) 。因此我们需要做的实际上是维护一个置换，之后对置换进行k次幂运算，最后重新排列d，进而计算出最终位置。

Atcoder Combination Lock

题意

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_e

题解

首先将字符串s中的每个字符减去'a'，这样字符的取值范围被限定到了0~25。

在字符串的前面加上一个字符0，尾部加上最后的一个字符。

比如序列[1,2,3,4]，修改后为[0,1,2,3,4,4]。

之后我们建立序列的差分形式d，即d[i]=s[i]-s[i-1]（d[0]=0）。

之后我们会发现区间[l,r]增加值操作变成了d[l]加上1和d[r+1]减去1。

现在考虑一个回文，假设i和j是沿着回文中心对称的两个坐标，那么必定有d[i+1]=-d[j]。

[...,a,b,...,b,a...]
[...,x,b-a,...,y,a-b,...]

现在我们会发现，我们希望通过在差分数组一些下标上加1，一些下标上减1，最后使得对于任意i，以及沿着中心对称的坐标j，满足d[i+1]+d[j]=0。

之后对于对称坐标对(i,j)，我们在二者之间连表。同时对于任意操作[l,r]，我们在坐标对(l,r+1)之间连边。这样对于任意连通块，连通块中顶点之间的值是共享的，我们需要平衡它们的值，使得对称坐标代表的顶点的值为0。这能成立当且仅当连通块中值之和为0。

这样问题就解决了。时间复杂度为$O(n)$。

AGC006D

题意

https://atcoder.jp/contests/agc006/tasks/agc006_d

题解

进行二分，考虑问题，最终值是否大于等于x。

这时候，序列中所有小于x的数标记为0，否则标记为1。我们发现如果两个连续的00、11出现，那么它们就不会再改变。

否则，如果0，1交替出现，那么在上面一层，0将变成1，1变成0。因此我们需要知道的就是位置n左右最近的连续的00、11出现的位置，哪个离中心近，哪个就会先占据中心位置，这意味着最终值为0或1。

剩下的就是二分了。

AGC043C

题意

https://atcoder.jp/contests/agc043/tasks/agc043_c

题解

每个顶点的权重公式保证了我们要按照编号之和从大到小将元素加入到最大独立集中。因此我们可以定义一个DP公式$f(i,j,k)$表示第编号为$(i,j,k)$的顶点是否在最大独立集中。

考虑另外一个平等博弈问题。有三个指标$i,j,k$，初始时都是0。两个人进行博弈，轮流操作，每次操作选择一个指标，将其增大（前提是有边）。一个人如果不能再操作，则认为失败。

对于上面提到的这个问题，我们也可以设计一个DP公式，$g(i,j,k)$表示指标为$i,j,k$的时候先手方是否必败。

我们会发现$g$和$f$拥有形同的边界值和相同的递推公式，因此我们可以直接用$g$代替$f$。

我们现在可以$O(n+m)$计算所有顶点的sg值，结果为：

\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[sg_1(i)\oplus sg_2(j)\oplus sg_3(k) = 0](10^{18})^{i+j+k}\]

注意到对于图$X$，我们可以将sg函数值相同的顶点合并。而总共只有$m$条边，因此顶点的sg值上界为$\sqrt{2m}$。利用这一点，我们可以记$s_1(i)=\sum_{j=1}^nsg_1(j)=i^i$，同理定义$s_2(j)$和$s_3(k)$，简化公式为：

\[\sum_{i=0}^{\sqrt{2m}}\sum_{j=0}^{\sqrt{2m}} s_1(i)s_2(j)s_3(i\oplus j)\]

于是乎，时间复杂度被优化到了$O(n+m)$。

AGC043D

题意

https://atcoder.jp/contests/agc043/tasks/agc043_d

题解

这道题的核心是发现，我们可以将整个生成的序列拆分成若干个递减子序列，而每个递减子序列的第一个元素按照子序列在整个序列中出现的前后关系递增。很显然对于给定的排序，其拆分是唯一的，因此子序列的数目和拆分数目是相同的。

我们可以$O(n)$解决将整个序列拆分成若干个长度不超过3的递减子序列（详情可以参考我的另外一篇博客《集合划分问题》中的子序列划分问题一节）。

但是这个问题有额外的限制，记$a,b,c$为分别拆分成长度为$1,2,3$的递减子序列的数目。那么一定有$b+c\leq n$。

因此我们可以稍微修改我们的DP公式，额外加一个维度就可以计算了，时间复杂度为$O(3n^2)$。

AGC035D

题意

https://atcoder.jp/contests/agc035/tasks/agc035_d

题意

给定一个$n$个元素的序列$a_1,\ldots,a_n$，其中$n\leq 18$，而$0\leq a_i\leq 10^9$。要求不断从中选择一个长度为3的子序列，并将中间元素删除，左右两个元素加上中间元素的值，之后放回原序列（之后左右两个元素时邻接的）。重复这个操作，直到剩下的元素数目为2。

问最后剩下的两个元素之和最小为多少。

题解

这道题的做法很有意思。我们可以这样玩，记$f(l,r,x,y)$表示考虑区间$a_l,\ldots,a_r$能产生的最小贡献，其中$a_{l-1}$产生的贡献次数为$x$，而$a_{r+1}$产生的贡献次数为$y$。可以推出转移公式

\[f(l,r,x,y)=\min_{i=l}^rf(l,i,x,x+y)+f(i,r,x+y,y)+(x+y)a_i\]

现在我们考虑有多少不同的状态。我们考虑当$l,r$确定的时候，会发现$(x,y)$最多有$2^{n-1}-1$种，我们可以构建一颗二叉树，每个顶点对应一个不同的$(x,y)$对，且会发现二叉树高度最多为$n-2$，因此可以得出结果。

我们可以直接用哈希表来记录状态。这样空间复杂度为$O(n^22^{n-1})$，时间复杂度为$O(n^32^{n-1})$。

ARC099 Eating Symbols Hard

题意

https://atcoder.jp/contests/arc099/tasks/arc099_d

题解

哈希的妙用题目。

我们可以把这$2\cdot 10^9+1$个数视作多项式的系数，即$f(x)=\sum A_ix^i$。这样我们就可以使用多项式哈希技术来解决这个问题了。

但是我们如何维护这个超大的多项式呢，考虑到哈希仅需要用到多项式在某点的点值，因此我们只需要对于特定的$x_0$，维护$y=f(x_0)$即可。

现在考虑四种操作：

  • $\tau_+(f)=f+1$
  • $\tau_-(f)=f-1$
  • $\tau_>(f)=f\cdot x_0$
  • $\tau_<(f)=f\cdot x_0^{-1}$

现在对于某个满足条件的区间$(i,j)$，考虑其对应的多项式为：

\[f_{i,j}(x)=\tau_{S_i}\cdot \ldots \cdot \tau_{S_j}(0)\]

我们希望这个多项式和应用完整序列后得到的多项式相同，即：

\[\tau_{S_i}\cdot \ldots \cdot \tau_{S_j}(0)=\tau_{S_1}\cdot \ldots \cdot \tau_{S_n}(0)=c\\\]

考虑到$\tau$是可逆函数，因此有：

\[\tau_{S_n}^{-1}\cdot \ldots \cdot \tau_{S_i}^{-1}\cdot \tau_{S_i}\cdot \ldots \cdot \tau_{S_j}(0)=\cdot \tau_{S_n}^{-1}\cdot \ldots \cdot \tau_{S_i}^{-1}(c)\\ \Rightarrow \tau_{S_n}^{-1}\cdot \ldots \cdot \tau_{S_{j+1}}^{-1}(0)=\tau_{S_n}^{-1}\cdot \ldots \cdot \tau_{S_i}^{-1}(c)\]

这里还需要注意到$\tau$是线性函数，即$\tau(x)=ax+b$，因此我们可以预处理出所有后缀。这样就能$O(n)$解决问题了。

ARC103D Distance Sums

题意

https://atcoder.jp/contests/arc103/tasks/arc103_d

题解

我们假设根顶点到其余所有顶点的距离之和最小。对于$D$属性最小的顶点一定是叶子，而我们记$size(i)$表示叶子$i$的子树大小。那么当我们从叶子$i$移动到父顶点$j$的时候，总距离会变成$D_j=D_i+2\cdot size(i)-n$。而考虑到每个顶点的$D$都不同，因此父亲顶点是唯一确定的。

最后还需要校验一次根顶点是否满足距离条件。

ARC091F

题意

https://atcoder.jp/contests/arc091/tasks/arc091_d

题解

考虑只有一堆石头的情况。我们考虑在石头大小为各个整数时的sg值。

  • 1~p-1，sg值均为0
  • p~2p-1，sg值0、1轮换。
  • 2p~3p-1，sg值0、1、2轮换。

可以看出这个问题和约瑟夫环相关，我们可以这样理解这个问题。一开始有$\lfloor n/k \rfloor+1$个整数，分别为0，1，…。我们有这些整数的一个循环排列，之后删除的数是$\lfloor n/k \rfloor$，问$\lfloor n/k \rfloor$的前$n\%k$个数在什么时候被删除。借由它的删除时间我们知道它的sg(n)具体是在第几个回合加入到上面的循环队列中，即这就是sg(n)函数。

剩下的就是一般的nim游戏了，时间复杂度为$O(n\sqrt{k}\ln k)$

ARC087E

题意

https://atcoder.jp/contests/arc087/tasks/arc087_c

题解

首先可以构建一株前缀树，我们统计不同深度可以加入的顶点数目，之后问题就转换成了取反游戏。

AGC20C

题意

https://atcoder.jp/contests/agc020/tasks/agc020_c

题解

要求求子集和的中位数。我们可以将$2^n$个子集配对，将$X$与$X-A$配对，即每个集合和自己的补集配对。于是我们得到了$2^{n-1}$个配对。记$S(A)$表示$\sum_{a\in A}a$，容易发现如果$X$与$Y$配对，那么$S(X)+S(Y)=S(A)$，不妨设$S(X)\leq S(Y)$，则一定有$S(X)\leq S(A)/2\leq S(Y)$。

如果有子集$X$满足$S(X)=S(A)/2$，那么结果一定是$S(A)/2$，否则则是最小的数$ans$，满足$ans>S(A)/2$，且存在子集和为$ans$。

nomura2020_D

题意

https://atcoder.jp/contests/nomura2020/tasks/nomura2020_d

题解

由于每条边都有出度1，可以发现最后每个连通块都会正好包含一个环。

可以发现对于某个赋值方案，其真正需要的边数为$N-C$，其中$C$为环数（成环意味着我们可以删除一条边）。因此我们实际上要做的就是统计具体有多少个环而已。

我们先把已知的边加上去，构造出若干个连通块。可以发现每个连通块要么有环，要么正好存在一个顶点$v$，$p(v)=-1$。对于已经有环的，我们可以直接处理掉。

接下来考虑所有第二类连通块（包含一个顶点$v$，$p(v)=-1$），设其所在连通块的大小为$a_1,\ldots,a_m$。

可以发现环可以分为两类，环中仅有一个第二类连通块，或者有多个。对于第$i$个第二类连通块，第一类环的数目为$(a_i-1)(N-1)^{K-1}$。接下来考虑第二类环，其中包含多个第二类连通块。可以发现环内部连通块的选择数目恰好为这些环的大小的乘积，因此就相当于我们要统计大小分别为$2,3,\ldots,m$的$a$的子集的乘积，这个可以通过动态规划求解，时间复杂度为$O(m^2)$。这里还需要注意一个子集可以构造多个不同的环，对于大小为$t$的子集，其可以构造$(t-1)!$个不同的环。

m_solutions2019_e

题目

https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e

题解

如果$d=0$，问题求的就是$x^n$非常简单。

否则我们知道当$d=1$的时候，问题要求的是$x(x+1)\ldots(x+n-1)=\frac{(x+n-1)!}{(x-1)!}$，我们只需要预处理阶乘就可以直接$O(1)$求解了。

否则当$d>1$的时候，就有$x(x+d)\ldots(x+(n-1)d)=d^n(\frac{x}{d}(\frac{x}{d}+1)\ldots(\frac{x}{d}+n-1))=d^n\frac{(\frac{x}{d}+n-1)!}{(\frac{x}{d}-1)!}$。

agc045_c

题目

https://atcoder.jp/contests/agc045/tasks/agc045_c

题解

由于我们可以将整个区间覆盖为0或1，因此我们可以始终假设$A\geq B$。之后如果我们将所有长度大于等于$B$的连续的$1$全部转换为0，则必定至少有一个长度达到$A$的连续的0。

我们可以通过统计有多少不合法的01序列来统计。记$f(n)$表示在长度为$n$的0序列上，只允许放1，有多少种不同的结果，可以发现：

\[f(n)=f(n-1)+\sum_{k=B}^nf(n-k-1)\]

这可以$O(n)$求出来。

之后考虑$dp(i,j,0)$表示在放了前$i$个数，其中0在尾部出现了$j$次，其中$A>j>0$。同理令$dp(i,j,1)$表示在放了前$i$个数，其中1在尾部出现了$j$次，其中$B>j>0$。

其中$dp$可以$O(n^2)$求解。

arc101_d

题目

https://atcoder.jp/contests/arc101/tasks/arc101_d?lang=en

题解

记$M$为所有坐标的上限。

问题实际上要我们为每个机器人赋予01，0表示从左侧第一个出口离开，1表示右侧第一个出口离开，设第$i$个机器人赋予的值为$v_i$。其中一些机器人只有一侧有出口，这些机器人不影响结果可以忽略。

之后我们记$p_i=(x_i,y_i)$表示第$i$个机器人距离左侧第一个出口的距离为$i$，距离右侧的第一个出口$y_i$。因此我们把问题丢到了二维平面上。

考虑这样一对点$p_i,p_j$，满足$x_i\leq x_j\land y_i\geq y_j$，即$p_i$落于$p_j$的左上侧矩形中，那么我们发现当机器人$j$从左侧离开时，一定有机器人$i$也从左侧离开，可以得出约束条件$v_i\leq v_j$。

好的，现在剩下的就是要求我们在满足所有约束条件的前提下，可以得到多少不同的赋值方案。

我们可以这样做，记$dp(i,j)$表示$x\leq i$所有点中，设置为$1$的点中纵坐标最大的为坐标$j$。因此可以发现$dp(i,0),\dots,dp(i,M)$统计了所有对$x\leq i$的点的有效赋值方案，且没有重复统计。接下来看转移，如果$(i,j)$没有点，则$dp(i,j)=dp(i-1,j)$，否则有$dp(i,j)=\sum_{k\leq j}dp(i-1,j)$。

我们可以先将所有平面点离散化，之后用BIT来维护DP。可以发现大部分情况都是第一种转移（直接继承），而每次进行第二种转移，需要消费掉至少一个点。因此总的时间复杂度为$O(n\log_2n)$。最后的总和就是$dp(M,0)+\ldots + dp(M,M)$。

tenka1_2019_f

题目

https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_f

题意

给定$n$和$x$，问存在多少不同的长度为$n$的序列，序列每个元素都是$0,1,2$，且序列的任意一段子串和均不等于$x$。

题解

一开始想了个$O(n^2\log_2n)$的算法，自然T了。后来看了题解，发现自己忽略了一个重要条件。

我们可以分别考虑存在多少长度为$k$的由$1,2$组成的序列满足没有子串和为$x$，记这个数目为$f(k)$。那么这些序列对结果的贡献为$f(k){n \choose k}$。因此我们需要做的就是算出$f(0),\ldots,f(n)$。

假设现在考虑长度为$k$的$1,2$组成的序列，分两种情况讨论：

  1. 序列总和$S$小于$x-1$
  2. 序列总和$S$大于等于$x-1$

对于第一种情况，可以直接枚举出$2$的出现次数小于$x-1-k$。之后可以发现存在$\sum_{i=0}^{x-2-k}{k\choose i}$种序列。

对于第二种情况，此时一定有一个前缀和正好等于$x-1$。我们再次枚举这个前缀的长度，记其为$L$。可以发现除了前面$L$个元素外，后面的$k-L$个元素都是$2$，同理前$k-L$个元素也都是$2$。可以得出这样的序列数目为${L-(k-L)\choose x-1-k-(k-L)}$。

上面的算法时间复杂度为$O(n^2)$，官方题解中好像还有一种$O(n)$的算法。

agc026_e

题目

https://atcoder.jp/contests/agc026/tasks/agc026_e

题解

真的难想。

记$a_i$表示第$i$个$a$出现的下标，$b_i$表示第$i$个$b$出现的下标。

我们可以将原序列分成若干块，每块拥有相同数目的$a$和$b$，且每一块中要么对所有$i$都满足$a_i>b_i$，要么满足$b_i>a_i$。

考虑$a_i<b_i$的情况，考虑此时能得到的字典序最大的字符串，这时候我们会选择$a_1,b_1$，以及$a_k,b_k,\ldots$，其中$k$是最小的下标，满足$a_k>b_1$，后面的同理。

考虑$a_i>b_i$的情况，考虑此时能得到的字典序最大的字符串。假如我们加入了字符$a_i$与$b_i$，我们可以证明$a_{i+1},b_{i+1}$一定被加入，因为可以使得字符串的字典序变的更大。因此我们枚举所有的$n$种可能的情况即可。这里的时间复杂度为$O(n^2)$。

最后我们考虑如何合并多块的解。我们优先加入第二类情况，我们将第二类情况的解进行排序（相同字典序，下标较小的优先）。之后选择最大字典序的字符串加入。最后可能剩下部分第一类情况的块可以被加入，全部加入即可。

这里需要证明一个条件，就是对于第二类情况的合并，我们只需要考虑每个块的最大字典序的串，因为其余串都不可能是它的前缀。这里证明一下：

考虑我们块的定义，我们将b对应+1，a对应-1，则一个块实际上是区间和为0的某个部分，且没有任意前缀和为0。之后我们证明如果块的长度超过$2$，则删除$a_1$和$b_1$后块的所有性质依旧满足，即没有任何（非空，非全部）前缀和为$0$。很显然如果有前缀和为$0$，记前缀长度为$2k$，则一定有$2k>a_1-2$。而这意味着加入$a_1$和$b_1$后长度为$2k+2$的前缀和为0，这与块的定义相悖。这意味着任意后缀的前缀和都不为0。因此我们也同时证明了其余串都可能是最大字典序串的前缀。