前言:
这里会分享一些精妙的组合计数题, 此类题往往需要选择合适的计数集合的划分方式, 有些计数角度的精妙, 个人感觉没有做过相对的题目, 或者是计数感足够犀利, 实在是很难想到正确的角度, 所以这里会汇总一些有趣的计数题, 希望可以帮助到一部分人
ARC168 C - Swap Characters
题意:
给定一个长度为\(N\), 且只包含A, B, C 的字符串\(S\), 我们可以做如下的操作不超过\(K\)次:
- 任意交换两个字符
问最后\(S\)可能变成的字符串有多少种?
思路:
乍一看这个条件其实很强劲, 我们可能上来会先想dp, 但是一定不要忘记只含有三种字符这个关键条件
我们将字符串\(S\)可能变成的结果字符串设为\(T\), 那么问题其实就转化为了:
- 有多少种字符串\(T\), 是可以通过对\(S\)进行不超过\(K\) 次操作得来?
不错! 好像前进了一步, 这样就可以自然地想出下一阶段的问题:
- 字符串\(S \rightarrow T\) 最少经过多少次变换?
那么我们只需要关心对应位置的关系, 我们设$f(x, y) := $ 有多少个位置pos, 使得\(S[pos] = x\), 并且\(T[pos] = y\), 那么首先我们只需要关心\(x != y\)的\(f\)值 (x, y 是字符)
首先如果\(f(x, y) > 0\), \(f(y, x) > 0\), 那么我们是不是可以交换这两个位置, 使得两个值都减一, 可以持续这样的操作, 直到有一方为0
结果就会变成\(f(A, B) = f(B, C) = f(C, A) = X\), \(f(A, C) = f(C, B) = f(B, A) = Y\), 且X和Y之中的其中一个肯定为0
不妨设\(X > 0\), 我们可以找到三个位置\((A, B, C) \rightarrow (B, C, A)\), 只需要进行两次交换操作, 此时X--
综上, 我们找到了将\(S\)变成\(T\)的方法, 通过这种方法, 我们似乎也可以找到一种对\(T\)的计数方式.
我们可以枚举\(f\) 的值, 具体地说, 可以分别枚举(A, B), (B, C), (A, C), (A, B, C)出现的次数, 前三对是操作1, 后面的是操作2, 操作2的代价是两次交换, 操作1的代价是一次交换,
得益于\(K\)的范围很小, 所以可以轻松解决