测试题目选集

依然暂无。

Miscellaneous

Atcoder AGC070B - Odd Namori

Submission #61312800 - AtCoder Grand Contest 070

Atcoder AGC070C - No Streak

对于 A 胜，B 胜和平局分别表示成 \(A,B,X\)，同时个数为 \(a,b,x\)。然后考虑首先解决前缀上 \(A\) 的个数始终大于等于 \(B\) 的问题。

考虑格路计数，设置一个三维的直角坐标系，\((a,b,x)\) 表示序列恰有 \(a\) 个 \(A\)，\(b\) 个 \(B\)，\(x\) 个 \(X\) 的的终点，而每次在末尾选择一个结果则是在三维上选择一个方向走一步，要求任何时候都有 \(a\ge b\)。那么格路计数会选择在第一个 \(a<b\) 的位置之后，在之后每次选择结果之后进行 \(A\to B,B\to A,X\to X\) 的翻转。显然终点也会被翻转，所以最后用无限制时到达 \((a,b,x)\) 的方案数减去任意到达 \((b-1,a+1,x)\) 的方案数即可。

回到原题，考虑要求不出现 \(AA\) 和 \(BB\)，那么记录 \(f(a,b,x)\) 表示 \(a\) 个 \(A\)，\(b\) 个 \(B\)，\(x\) 个 \(X\) 时，要求不出现 \(AA,BB\) 的方案数，我们会有一个大概的想法是用 \(f(a,b,x)-f(b-1,a+1,x)\) 来表示答案。但是会存在一些问题：

会发现，翻转前后对于连续出现要求的满足，实际上是几乎一致的。但是不同之处仅仅在于翻转时可能出现的：原本是 \(BB\) 而变成 \(BA\)，这在 \(f(a,b,x)\) 中一定不会被统计，但却会在 \(f(b-1,a+1,x)\) 中可能会被统计若干次；原本是 \(BA\) 而被翻转成 \(BB\)，这在 \(f(a,b,x)\) 中可能会被统计若干次，但在 \(f(b-1,a+1,x)\) 中却不会被统计。然后我们就希望具体求出一个 \(I\)，满足 \(f(a,b,x)-I\) 就是答案。

考虑 \(I\) 中应该包含什么情况，发现，应该是在某个 \(B\) 之后第一次满足当前 \(a<b\)，然后紧随其后跟着一个 \(X\) 或者一个 \(B\)，并最终到达 \((b-1,a+1,x)\)。这两个情况包含翻转前 \(f(a,b,x)\) 中出现的 \(BX\) 和 \(BA\)，但翻转前的 \(BB\) 因为没有被统计，所以在 \(I\) 中也不能统计。

那么 \(I\) 就等于上述两种情况的方案数之和。

• 考虑 \(BB\)，那么可以考虑将 \(BB\) 看成是一个 \(B\)，这样的方案数是完全和 \(f(b-1,a,x)\) 相等的，因为在第一个 \(a<b\) 的位置之后增减 \(B\) 显然是有操作的互逆性的，因此构成双射。

• 考虑 \(BX\)，首先可能会想到将 \(X\) 踢掉，但是如果是形如 \(BXB\) 的形式那么 \(X\) 实际上踢掉之后剩下 \(BB\) 是不会出现在 \(f(b-1,a+1,x-1)\) 中的，因此仍然需要分类讨论。

  • 如果形如 \(BXB\)，那么就可以连续踢掉后面的 \(XB\)，不难发现仍然合法，显然和 \(f(b-1,a,x-1)\) 中的方案构成双射。
  • 如果形如 \(BXA\) 或者 \(BXX\)，那么就可以只踢掉 \(X\)，所以这部分方案应该等于 \(f(b-1,a+1,x-1)\)。

那么就可以得到 \(I=f(b-1,a,x)+f(b-1,a,x-1)+f(b-1,a+1,x-1)\)。那么答案就是 \(f(a,b,x)-f(b-1,a,x)-f(b-1,a,x-1)-f(b-1,a+1,x-1)\)。

随后考虑 \(f(a,b,x)\) 怎么求。因为 \(a,b\) 可以交换，不妨设 \(a>0,b\ge 0\)（剩余情况是简单的）。那么枚举有多少 \(A|A\) 之间没有 \(X\)，设为 \(k\)，应该有 \(0\le k < a\)。那么这部分的情况是 \({a-1\choose k}\) 的。然后考虑有 \(a-k+1\) 个位置可以填 \(X\)，且其中 \(a-k-1\) 个位置必须至少有一个 \(X\)，那么方案数是 \({x+1\choose a-k}\) 的。最后考虑填上 \(B\)，有 \(k\) 个位置必须填上 \(B\)，剩余 \(a+x+1-k\) 个位置最多填上一个 \(B\)，那么应该有方案数 \({a+x+1-k\choose b-k}\)。那么 \(f(a,b,x)=\sum_{k=0}^{a-1}{a-1\choose k}{x+1\choose a-k}{a+x+1-k\choose b-k}+[a=0]{x+1\choose b}\)。

可以 \(O(n)\) 计算。

Submission #61316013 - AtCoder Grand Contest 070