【题解】AGC 039

C

操作相当于将串最后一个字符取反后丢到最前面。

首先可以发现操作了 \(2n\) 次后必定还原,不过有些串可以不用操作这么多次。具体考虑串 \(S+A\),满足 \(S‘+A‘=A‘+S\),其中 \(S‘,A‘\) 分别代表 \(S,A\) 逐位取反后得到的串,此时操作 \(2|A|\) 次就能还原。

继续推,如果有 \(S‘+A‘=A‘+S\),说明 \(S\)\(A\) 这个前缀以及 \(A\) 这个后缀,不断反复的推可以发现,\(S\) 一定能表示为 \(A+A‘+\cdots +A+A‘+A\) 的形式,对于一个 \(S\),要找的其实就是最短的 \(A\)

先不考虑是否是最短,令 \(f_i\) 表示 \(|A|=i\) 时满足上述形式的 \(S\) 的个数,后面做一个简单容斥就能得到 \(g_i\) 表示 \(|A|=i\) 作为最短满足要求的 \(A\)\(S\) 的个数。至于求 \(f_i\) 只需要额外讨论 \(A\)\(N\) 长度为 \(i\) 的前缀时是否满足要求即可,剩下的都很好办。

D

计算几何不做!

E

牛逼题。

考虑连边 \((1,i)\) 将圆划为了两部分 \([2,i),(i,n]\),这两部分中一定存在 \(k\geq 1\) 条连边,且满足:\(2\leq p_1<p_2\cdots<p_k<i\)\(n\geq q_1>q_2\cdots>q_k>i\)\(k\) 条连边即为 \((p_i,q_i),1\leq i\leq k\)

此时考虑 \((p_1,q_1)\),注意到因为不成环,所以一定存在一个 \(t_1\geq p_1\) 满足 \([2, t_2]\) 中的点组成的连边和 \((p_1,q_1)\) 相交形成子树,\((t_1,i)\) 中的点不会和前面的点相交,同理对于 \(q_1\) 存在一个 \(t_2\)

\(f_{l,i,r}\) 表示区间 \(l,r\) 只有 \(i\) 向外连边,剩下的连边和 \(i\) 的连边相交的合法方案数,注意到这样我们将原问题分成了三个部分:\(f_{2,p_1,t_1},f_{t_2,q_1,n},f_{t_1+1,i,t_2-1}\),这也就是转移了。具体实现的时候最好考虑最下面的连边,即 \((p_k,q_k)\)

本题主要难点在于如何将原问题划分子问题,从简单情况(关于 \(1\) 的连边)之类的地方下手,然后总结一般的连边方式,从而将原问题拆为多个子问题,然后用 dp 解决问题。

时间复杂度 \(O(n^7)\) 但是常数极小,可以通过优化实现更加优秀的复杂度,这里就不讨论了。

代码:Submission #25463109 - AtCoder Grand Contest 039

F

计数题。

注意,本文讨论的所有矩阵大小均为 \(n\times m\),且每个数取值为 \([1,k]\) 中的整数。

考虑 \(\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f(i,j)\) 的组合意义。考虑到每一个原矩阵都对应一个 \(f\) 矩阵,对于两个矩阵 \(A,B\),定义 \(A\leq B\) 当且仅当 \(\forall i\in[1,n],j\in[1,m],A_{i,j}\leq B_{i,j}\),那么上式的意义即为 \(\sum\limits_{A}[A\leq B]\),所以不妨从 \(A\) 的角度计算 \(B\)

考虑一个矩阵 \(A\),此时 \(A_{i,j}\) 对原矩阵的限制即为:原矩阵第 \(i\) 行,第 \(j\) 列所有的元素不小于 \(A_{i,j}\) 。而我们要求的就是满足所有 \(A_{i,j}\) 的限制的原矩阵的个数。

注意到上述的限制还可以简化,每个矩阵 \(A\) 可以用两个长度分别为 \(n,m\) 的序列来表示:\(L_{1,i}=\max\limits_{j} A_{i,j},i\in[1,n]\) 以及 \(L_{2,j}=\max\limits_{i}A_{i,j},j\in[1,m]\),最终原矩阵 \(T\) 中关于 \(T_{i,j}\) 的限制即为 \(T_{i,j}\geq \max(L_{1,i},L_{2,j})\)

现在有两个问题:1. 怎么求每个 \(\{L_1,L_2\}\) 对应多少个 \(A\) 。2. 怎么求每个 \(\{L_1,L_2\}\) 作为限制时有多少满足限制的 \(T\)

第二问很好解决,只需要令 \(f_{v,a,b}\) 表示考虑到了权值 \(v\in[1,k]\),满足 \(\sum\limits_{i}[L_{1,i}\leq v]=a,\sum\limits_{j}[L_{2,j}\leq v]=b\) 条件的 \(\{L_1,L_2\}\)(我们称这 \(a\) 行和 \(b\) 列相交形成的子矩阵为"确定的子矩阵"),现在"确定的子矩阵"的个数。

看上去这个做法至少 \(O(kn^2m^2)\) 起步。不过可以发现,在转移 \(f_{v,a,b}\) 时,对于行的转移和对于列的转移时可以分开的,也就是说将转移分成两步,先转移行,再转移列,那么这下复杂度为 \(O(knm(n+m))\)

对于第一问,接下来似乎只有一条路可以走:在求 \(f_{v,a,b}\) 时,同时解决第一个问题。具体的,对于 \(f_{v,a,b}\),如果 \(A\) 的某个位置被这 \(a\)\(b\) 列覆盖到了,那么称其为"确定的位置"。假设现在更新 \(f_{v,a,b}\),新增了 \(c\) 行和 \(d\)\(L_{-,-}=v\) 的,也就新增了若干个"确定的位置",现在的问题就是求出这些新增的"确定的位置"的方案数。

因为求的是"最大值恰好为 \(v\)",不妨考虑容斥,枚举一定不合法的行列数,系数为:

\[\sum_{i=0}^{c}\sum_{j=0}^{d}(-1)^{i+j}(v-1)^{i(m-b)+j(n-a-i)}v^{(c-i)(m-b-j)+(d-j)(n-a-c)} \]

当然转移还需要乘上一个方案数 \({n-a\choose c}{m-b\choose d}\)

注意到这个转移同样可以分四步转移,我是按照:1. 容斥的 \(i\) 行。2. 容斥的 \(j\) 列。3. 不容斥的 \(c-i\) 行。4.不容斥的 \(d-j\) 列。的顺序做的。最终复杂度仍然为 \(O(knm(n+m))\)

代码:Submission #25473002 - AtCoder Grand Contest 039,轻微卡常。

正解做法是这个做法的 \(\frac{1}{2}\) 常数,有空研究。

【题解】AGC 039

上一篇:如何查看windows的系统运行时间


下一篇:FM17550