计数题目选做

AT_agc040_c Neither AB nor BA

题目大意：

一个由 \(ABC\) 构成的串是好的，当且仅当可以通过不删 \(AB\) 和 \(BA\) 的相邻的两个字符把它删空。
现在给定 \(n\)，求长度为 \(n\) 的字符串有多少是好的。
\(n \le 10^7,2 | n\)。

解题思路：

首先注意到 \(C\) 这个字符是没有施加任何限制的，所以可以看成任意填 \(A/B\)。
那么现在变成了如何判定一个 \(AB\) 串是否合法。
因为 \(AA\) 和 \(BB\) 形的 删除可能导致了 \(ABABABABAB\) 这种数量很多但不能删的情况。
也就是这样刻画会非常复杂。

但注意到因为是一次删两个，所以奇偶性永远不会变。
这样我们就找到了永恒的东西。

然后套套路，将偶数位置的 \(A/B\) 切换，那么一次就是删一个 \(AB/BA\) 了。
这样就很好了啊，因为只要 \(A,B\) 同时有，就一定会相交。

相交就意味着一定可以删除。
所以现在的问题就变为了 \(AB\) 不能有绝对众数，\(C\) 这时候就是用来平衡的了。

因为不能有绝对众数，而绝对众数只能有一个，所以简单容斥一下就好了。
\(O(n)\)。

AT_agc020_f Arcs on a Circle

题目大意：

你有 \(n\) 个线段，每个线段长度给定，现在在一个环上，每个线段的初始坐标在实数范围内随机，求覆盖整个环的概率。
\(n \le 6, L \le 50\)。

解题思路：

遇到小数部分，直接套路地枚举大小关系，然后这个题直接状压就行了。
\(O(2^n \times n! \times n^2 \times L^2)\)

AT_agc019_f Yes or No

题目大意：

已知一套试卷中有 \(N\) 个选 \(A\)，\(M\) 个选 \(B\)，你知道，需要逐一蒙 \(N+M\) 个题，而且你每蒙完一个就会给出这个题的答案。
而且答案在一开始就随机定了，问你期望答对多少题。
\(N,M \le 5 \times 10^5\)

解题思路：

首先我们肯定是要知道我们要怎么填这个答案，策略显然是填剩下多的那个。
于是我们就有一个网格图，往左走表示选 \(Yes\)，往右走表示选 \(No\)，由于 \(N,M\) 是对称的，所以不妨设 \(N > M\)。
所以我们的最优策略就会如下图红线一样（蓝线代表斜对角）

我们现在就是要求的每一条路径于红线交的期望数量。
考虑这个折线中横着的太难看了，而把他们去掉之后正好是一层一层的。
所以就是单独算这些的贡献然后加 \(N\)。
\(O(n)\)。

不过这种拆图形的手法让我想起来 NOIP t4 了？

AT_agc056_b Range Argmax

题目大意：

有一个未知的长度为 \(n\) 的排列 \(p\) 和 \(m\) 个区间 \(l_{i} \sim r_{i}\)，设 \(q_{i}\) 表示 \(l_{i} \sim r_{i}\) 中最大值的位置。
求有多少种不同的 \(q\)。
\(n \le 300, m \le \frac{n \times (n - 1)}{2}\)

解题思路：

因为不同的 \(p\) 所对应的 \(q\) 序列可能会有重复的，所以我们希望找到一个双射关系。

注意到这个题区间内和区间外是相对独立的，所以考虑区间 \(dp\)。

一个 naive 的想法是枚举第一个出现在这个区间内的条件所对应的 \(q_{i}\)，但发现把他切开后左右会影响他，他也会影响左右，非常麻烦。
所以还是老老实实来枚举最大值的位置了，这样就不会有左右的区间来影响这个了。

但这样子还会算重，因为你的区间内部是“局限的”，你先定 \(i\) 再定 \(j\) 和先定 \(j\) 再定 \(i\) 就会算重一次。
还是去重的经典套路，类似先来后到的钦定方式，你前面的钦定不对后面的钦定造成影响，而后面的钦定会对前面的钦定造成限制。

想一下具体是什么限制，考虑两个给定的区间一前一后分别为 \(i,j\) 且他俩有交，而最大值的位置定在了 \(j\) 里面，此时如果 \(i\) 内部的最大值在 \(j\) 中，这个钦定顺序就是唯一的，但要是不在的话重复了，自然地，设 \(dp_{l,r,k}\) 表示 \(l \sim r\) 内，最大值的位置 \(\ge k\) 的方案数。

转移是简单的，\(O(n^3)\)。

AT_agc056_e Cheese

题目大意：

有一个长度为 \(n\) 的圆，在 \((0 \sim n - 1) + 0.5\) 这些位置都有一个老鼠，你现在有 \(n-1\) 个奶酪，有 \(a_{i} \text{%}\) 的概率投放在 \(i\) 这个位置并开始顺时针移动。
每遇到一只没吃到奶酪的老鼠，都有 \(\frac{1}{2}\) 的概率被吃掉，奶酪会一直转下去，直到每吃掉。
现在问每个老鼠最后饿肚子的概率为多少。
\(n \le 40\)。

解题思路：

非常牛的想法。
考虑这个相当于若干个 \(1/2\) 乘起来，由于是否被吃的概率都是 \(1/2\)，所以我们直接设 \((i,x)\) 表示 \(i\) 经过 \(x\) 的概率，也就是 \(1/2\)。
那么现在相当于若干个条件：

\[\begin{matrix} (1,s_{1}),(1,s_{1}+1) \sim (1,t_{1}) \\ \dots \\ (n-1,s_{n-1}),(n-1,s_{n-1}+1) \sim (n-1,t_{n-1}) \end{matrix} \]

然后我们发现这些都是可以交换顺序的！！！
比如 \((x,k)\) 和 \((y,k)\)，如果 \(x\) 没吃 \(k\) 且 \(y\) 没吃 \(k\)，那么显然互不影响，而若 \(y\) 吃了 \(k\)，就相当于交换了 \(x\) 和 \(y\) 这两只老鼠，还是没有问题！！！

通过这个交换律，我们就可以顺着 dp 了。
考虑枚举 \(i\) 表示要算 \(i\) 的答案，那么我们为了避免 “无限” 这个东西，我们考虑让这些奶酪活着跑到 \(i\) 这个地方然后开始用数学。
由于这些满足可交换性，所以我们从前往后 dp 就是对的，具体的，设 \(dp_{i,j,k}\) 表示填了前 \(i\) 个位置，已经填了 \(j\) 个奶酪，有 \(k\) 个被 Jerry 吃了的概率。

至于后面的数学部分，可以通过等比数列算一下。
\(O(n^5)\)

AT_agc064_d Red and Blue Chips

题目大意：

有一个长度为 \(n\) 的由 \(RB\) 构成的串 \(T\)，初始有 \(n\) 个字符串 \(S\)，\(S_{i}\) 初始为 \(T_{i}\) 这个字符。
现在从 \(1 \le i < n\) 的每个 \(i\)，依次选一个 \(i < j \le n\)，且 \(T_{j} = B\)，将 \(S_{i}\) 拼到 \(S_{j}\) 前面。
保证 \(T_{n} = B\)，求 \(S_{n}\) 最后有多少不同的可能。
\(n \le 300\)。

解题思路：

套路地，我们要么考虑去对应两个选择方式，要么去考虑如何判定一个串是否合法。

由于树的 dfs 序列的结构过于复杂，我们难以维护，所以我们优先考虑它的判定开始。
怎么判定呢？考虑先手玩一下过程，对于 \(n\) 前面那连续的 \(R\) 段我们肯定是要放在答案串最前面。

这启示我们从后往前挨个插入。
然后就遇到了一个 \(B\)，它肯定是插在 \(n\) 前面的，但对于它后面跟着的这段 \(R\) 就不一定了，可能插在它和 \(n\) 之间，可能插在它的前面，可能两个都插了。
对于它插在了这个 \(R\) 前面的这部分，自然地与第一段地这个 \(R\) 成了一段，且通过我们 \(B\) 的插入位置来看，他们在最后也会是一段。

插入过程明了了，那么开始判定了，首先答案串的最后一个要为 \(B\) 并且 \(RB\) 个数与原串一样。
这时候我们从前往后扫描这个答案串，设原串中的 \(R\) 段的长度分别为 \(b_{1}, b_{2}, \dots b_{m}\)，而且这些准确来说是每个 \(B\) 前面的，也可以为空。
那么对于答案串的第一段 \(R\)，它的长度要大于等于 \(b_{m}\)，可对于 \(b_{m-1}\)，他就放飞自我了。
因为除了最后一段，他在答案串中都有可能有 \(B\) 在它前面。

这时候我们需要关心它在插入的时候会在哪一段，但可能会出现在任意一段，所以要保证存在后面的一个段满足和第一段加一块的长度 \(\ge b_{m} + b_{m-1}\)。
而我们对于 \(b_{m-2}\) 同理，那么贪心地想，就是除了第一段以外选最长，次长，次次长 \(\dots\)。

所以设 \(dp_{len,i,j}\) 表示在长度 \(\ge len\) 的段里，凑了 \(i\) 段，总和为 \(j\) 的方案。
\(O(n^3 \ln n)\)。

AT_agc039_f Min Product Sum

题目大意：

有一个 \(n \times m\) 的棋盘，你要在每个位置填一个不超过 \(k\) 的数，设 \(r_{i}\) 表示第 \(i\) 行的最小值，\(c_{i}\) 表示第 \(i\) 列的最小值，求：

\[\sum \prod_{i,j} \min(r_{i},c_{j}) \]

\(n,m,k \le 100\)。

解题思路：

考虑直接对 \(A\) 棋盘进行计数是困难的，考虑对 \(r_{i},c_{j}\) 进行计数，然后相当于对 \(A\) 棋盘的每一个位置进行一个限制，而恰好就可以套路地被容斥消掉。
然后对于 \(A_{i,j}\) 的限制就是 \(A_{i,j} \ge \max(r_{i},c_{j})\)，由于是由大的限制的，而且所有的位置都是等价的，考虑一点一点剥去最大的 \(r/c\)，然后通过组合数计算。

剥去就对应着添加（虽然二者都能 dp），我们设 \(dp_{t,i,j}\) 表示填了 \(r \le t\) 的行，\(c \le t\) 的列，分别有 \(i\) 行和 \(j\) 列的贡献总和。
那么考虑 \(t\) 向 \(t + 1\) 转移，枚举 \(t + 1\) 有多少正常的行，被钦定容斥的行，正常的列，被钦定容斥的列，转移注意系数。
\(O(n^3m^3k)\)，常数很小，但太唐了，过不去。

考虑这些都是互不关联的，所以你可以分阶段 \(dp\) 一下，但注意一定要先搞正常的再搞不正常的，因为不正常的限制更大。
\(O(nmk \times (n+m))\)。

AT_agc039_e Pairing Points

题目大意：

有一个长度为 \(2n\) 的环，每个整数点都是一个关键点，你要在他们之间连 \(n\) 条边，要满足一个点恰好要往外连一条边。
你要保证连出来的这些边构成树，同时有一个矩阵，表示每个点对之间能否连边。
求有多少种方案。
\(n \le 20\)

解题思路：

考虑树这个东西是很难刻画的，和非常的难判定，但由于 \(n\) 才 20，不妨去随便枚举一些东西。
注意到区间内是相对独立的，只会有几条边连出去，可是现在是环，那么我们只需要枚举一下一号点与哪个点连就可以了。

这样左右就都变成区间了，而我们注意到如果令穿过我们枚举的这条边的边成为关键边，那么关键边之间不交，而且非关键边只会交不超两个关键边！

因为树上去掉一条边之后就会影响一定的连通性！！！

而对于关键边来说，与他联通的一定是一段区间。
那么设 \(dp_{l,r,k}\) 表示 \(l \sim r\) 这段区间，\(k\) 是内部往外连的边的端点。
这样随便枚举枚举就是 \(O(n^7)\) 了，常数极小，可以通过。

所以这题的顶级思想还是通过枚举打消他们之间的联系啊！！