CF 1735D

题目内容

给定一副有 $n$ 张的手牌，每张牌有 $k$ 种属性，每种特征的取值只能为 $0, 1, 2$ 中的一个。我们称三张牌组成一组顺子，当且仅当：三张牌的某一种属性要么相同，要么两两不同，这对于所有 $k$ 种性质成立。另称五张牌组成一组“元（meta）顺子”，当且仅当可以从这五张牌中组出至少两组顺子，求元顺子的个数。

特殊数据范围： $1 \leq n \leq 1000$ ， $1 \leq k \leq 20$ 。

解法

提示

可以得到能够组出三组或更多顺子的元顺子吗？给出严格证明。

解答

答案是不能。考虑反证，为了使五张牌能够得到至少三组顺子，我们需要两张牌被这三组顺子共用。考虑这种情况下顺子中的“单张”：对于任意一个属性，若为两两不同，则共用的一对占用了两种属性，单张只有一种属性可选；全部相同同理，单张也只有一种属性可选，因此对于一对给定的牌，两张牌都能够与它们构成顺子当且仅当两张牌相同，因此我们不能构造出多组顺子公用两张牌的情况，五张牌最多只能包含两组顺子，因此元顺子中有且仅有一张牌被两组顺子公用。

接下来就简单很多了。看到这么小的数据范围，考虑直接暴力枚举出所有的顺子。随后枚举所有的牌，考虑若其作为中心牌被 $k$ 组顺子共用，依据计数原理显然能够组出 $(\binom{k}{2})$ 组元顺子。依据上面证明的性质，对于不同的中心牌，能够构造出的超顺子一定不同，于是可以放心加和而不用担心重复。

AC 代码

见提交记录。