自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:31:05，当前版本为作者最后更新于2021-05-04 15:55:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

给定 $n$ 个字符串 $S_i$，定义一个字符串三元组 $(s_1,s_2,s_3)$ 是合法的当且仅当：

• $s_1,s_2,s_3$ 的首字母是 M，C，O 和 I 中的一个。
• $s_1,s_2,s_3$ 的首字母互不相同。

求有多少组合法的字符串三元组。

$1 \le n \le 10^5$，$1 \le |S_i| \le 11$。

Solution

Subtask 1：铃太强了，你需要输出 $0$。

Subtask 2：暴力枚举，$\mathcal O(n^3)$。

正解：暴力枚举 M，C，O 与 I 的个数，设其分别为 $m,c,o,i$，那么通过小学排列计数就可以知道答案可以分为四个部分：MCO，MOI，MCI，COI，将其组合而成即可：

$$m \times c \times o+m \times c \times i+m \times o \times i+c \times o \times i $$

这个是可以 $\mathcal O(n)$ 计算的。