MCOI R5 A 题解

一只书虫仔 · 2021-05-04 15:55:22 · 题解

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

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

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) 计算的。