ARC 140
打得很烂。Rank 590，Performance 1696。
D - One to One
每个点都有恰好一个出边，所以这是一个外向基环森林。因此连通块数就等于环的个数，我们只需要求出所有方案中环的个数的总和。直接算比较难办，考虑算每个环对答案的贡献。
首先，假如忽略掉 \(A_i=-1\) 的连通块，剩下的环是一定存在的，可以预先加到答案里。然后，观察到任意一个点数为 \(k\) 的、由 \(A_i=-1\) 的连通块组成的环，都会出现在 \(n^{c-k}\) 种方案里，其中 \(c\) 是 \(A_i=-1\) 的 \(i\) 的个数。接下来就是要计算出，对于所有 \(k=1,2,\dots,c\)，点数为 \(k\) 的环有多少个。
假如我们任取 \(k\) 个 \(A_i=-1\) 的 \(i\)，并设它们所在的连通块大小为 \(s_1,s_2,\dots,s_k\)，那么这 \(k\) 个连通块可以组成 \((k-1)!\prod_{i=1}^k s_i\) 种不同的环，且这些环上都恰好有 \(k\) 个 \(A_i=-1\) 的位置。所以，可以直接 dp（或者分治 fft）算出环的个数，并求出答案。
时间复杂度 \(\mathcal{O}(n^2)\)（dp）或者 \(\mathcal{O}(n\log^2 n)\)（分治 fft）。
ARC 141
Rank 164，Performance 2313。
A - Periodic Number
我做麻烦了。首先，假如 \(N\ge 99\)，一个显然的答案是 \(99\dots 9\)。枚举 \(N\) 的每个前缀 \(N'\)，只需要检查 \(N'\) 循环拼接和 \(N'-1\) 循环拼接是否合法即可。
ABC 260
Rank 167，Performance 2305。
G - Scalene Triangle Area
在 \((1,1)\) 处执行一次区域加，会形成如下图形：
++++++
++++00
++0000
000000
二维差分后，得到：
+00000-0
0000-0+0
00-0+000
-0+00000
相当于在 \((u,v)\) 处单点加一，并在两条斜率为 \(\frac{1}{2}\) 的线段上 \(\pm 1\)。线段加减可以再进行一次差分：先将线段的开始位置 \(\pm 1\)，并将线段的结束位置后面 \(\mp 1\)。所有操作执行完后，设 \(S_{i,j}\) 表示当前 \((i,j)\) 位置的值，我们从小到大枚举 \(j\)，令 \(S_{i,j}\gets S_{i,j}+S_{i+1,j-2}\)，也就是斜着做一次前缀和。
最终再做一次二维前缀和即可。时间复杂度 \(O(N^2+Q)\)。
AGC 058
Rank 106，Performance 2722。
A - Make it Zigzag
喜报：我的做法被我自己叉了！
以下是正确做法：
考虑第一个不合法的奇数位置 \(i\)，那么有 \(P_i>P_{i+1}\)。
- 若 \(P_i>P_{i+2}\)，则交换 \(P_i,P_{i+1}\)；
- 否则，交换 \(P_{i+1},P_{i+2}\)。
偶数位置同理。每次操作会使得第一个不合法的位置至少后移两位，因此操作次数 \(\le N\)。
B - Adjacent Chmax
对于每个位置 \(i\)，设
\[l_i=\max_{j<i\land P_j>P_i} \{j\},\\ r_i=\min_{j>i\land P_j>P_i} \{j\}. \]现在，问题转化成了：对于每个 \(i\)，你可以用 \(P_i\) 覆盖 \((l_i,r_i)\) 中的一段子区间 \([L_i,R_i]\)，且你需要保证 \(\forall i>1,L_i=R_{i-1}+1\)。问最终能得到多少种不同的序列。
设 \(f_{i,j}\) 表示用 \(P_{1\dots i}\) 覆盖长度为 \(j\) 的满足上述条件的序列，能得到多少种不同的序列。直接转移即可，时间复杂度 \(O(N^2)\)。
D - Yet Another ABC String
考虑容斥。将 \(S\) 划分为极长的 ABCABC... 的子串，设其中有 \(k\) 个长度 \(\ge 3\) 的段，令其容斥系数为 \((-1)^k\)。
枚举 \(k\)，我们要计算满足上述条件的字符串个数。若 \(S\) 开头的段长度 \(\ge 3\)，那么 \(S\) 开头填 ABC，BCA 或 CAB 均可。对于在中间的一段，因为我们需要保证每段都是极长的，所以这个段的开头三个字符只有两种填法。若开头的长度 \(\ge 3\)，方案数为 \(3\times 2^{k-1}\times \dbinom{a+b+c-2k}{\begin{matrix} a-k & b-k & c-k & k\end{matrix}}\)；对于另一种情况，计算是类似的。
时间复杂度 \(O(a+b+c)\)。
标签：dots,AtCoder,连通,比赛,记录,复杂度,Rank,ge,Performance From： https://www.cnblogs.com/alan-zhao-2007/p/atcoder-contest.html