https://codeforces.com/bestRatingChanges/18546898
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A
我们将 BBB 分为 nnn 组，每组分别为 [1],[1,2],[1,2,3],[1,2,3,4],...,[1,2,3,...,n][1],[1,2],[1,2,3],[1,2,3,4],...,[1,2,3,...,n][1],[1,2],[1,2,3],[1,2,3,4],...,[1,2,3,...,n]。
显然，有以下两种情况：
* AAA 在某些组内。显然，这种情况的 AAA 为 [...,Am−1,Am][...,A_{m-1},A_{m}][...,Am−1 ,Am ]，即满足 Ai=Ai−1+1A_i=A_{i-1}+1Ai =Ai−1 +1，在 BBB 中出现了 n−Am+1n-A_m+1n−Am +1 次。
* AAA 在某两个组之间。显然，这种情况 AAA 不满足上面的性质，并且在 BBB 中只出现了 111 次。
代码如下：
时间复杂度：O(tm)O(tm)O(tm)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B
怎么 B 题就这么逆天。
注意到当第 iii 个人进行完操作后后面的人都会重复执行这些操作。由于是结束后再染色，所以考虑最后一个操作的不同对后面的人的影响。
* 操作 A\tt{A}A：没有影响，该往后 111 格就往后 111 格。
* 操作 B\tt{B}B：染黑了后会前进 111 格，然后再到后面的白色格子。
所以可以递推解决。
时间复杂度：O(∑n+mlog(n+m))O(\sum n+m\log (n+m))O(∑n+mlog(n+m))。
C
我不知道啊，随便蒙了个结论。
呃就是先进 kkk 个人然后出 111 进 111 出 111 进 111 最后全出就行了，我不会证，但也想不到更好的办法了。
呃呃呃。
呃呃呃呃呃呃呃。
然后乱搞。
时间复杂度：O(∑n)O(\sum n)O(∑n)。
D
这个我是真会。
自己模拟一下，可以发现第 iii 列只能有一个黑格，并且必须在前 min{i,n−i+1}\min\{i,n-i+1\}min{i,n−i+1} 行之内。
然后范围就是一个到三角形。
注意到后面的格子在前面的格子中也有，所以我们可以倒着计算。
对于第 iii 行，一共有 (n−2×(i−1)−∑i+1nAiAi)n-2\times (i-1)-\sum_{i+1}^n A_i\choose A_i(Ai n−2×(i−1)−∑i+1n Ai ) 中情况。
乘起来就行了。
注意特判不合法的情况。
时间复杂度：O(∑n)O(\sum n)O(∑n)。
