分数: 266 分
问题陈述
高桥在该大学的研究支持中心工作。 N 实验室,每个实验室都致力于多个研究主题。实验室 i (1 \leq i \leq N) 正在研究 M_i 研究主题,每个主题由一串小写英文字母表示 W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}。请注意,同一研究主题不会在同一实验室内出现多次。
为了促进合作研究,该大学决定调查“有资格合作”的实验室。让 S_i = \{W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}\} 是实验室的研究主题集 i 正在处理。两个实验室 i, j (i \neq j) 被认为是“有资格合作”,如果双方共同的研究主题数量 S_i 和 S_j 至少 K,即 |S_i \cap S_j| \geq K 成立。这里,两个研究主题是否相同取决于它们的代表字符串是否完全匹配。
高桥列出了每个实验室正在研究的研究主题。根据此信息,找到“有资格合作”的实验室对的数量。请注意,这对实验室 i 和实验室 j 被认为与实验室对相同 j 和实验室 i。计算对的数量 (i, j) 满意 1 \leq i < j \leq N 满足条件。
约束
- 2 \leq N \leq 500
- 1 \leq K \leq 50
- 1 \leq M_i \leq 50 (1 \leq i \leq N)
- W_{i,j} 是长度介于 1 和 20 仅由小写英文字母组成 (1 \leq i \leq N, 1 \leq j \leq M_i)
- 同一研究主题不会在同一实验室内出现多次(也就是说,如果 j \neq k 然后 W_{i,j} \neq W_{i,k})
输入
输入由以下格式的标准输入给出。
N K
M_1
W_{1,1} W_{1,2} \ldots W_{1,M_1}
M_2
W_{2,1} W_{2,2} \ldots W_{2,M_2}
\vdots
M_N
W_{N,1} W_{N,2} \ldots W_{N,M_N}
第一行包含实验室数量 N 和阈值 K 用于确定“协作资格”,以空格分隔。
然后,对于每个实验室 i (i = 1, 2, \ldots, N),以下 2 行按顺序给出:
- 第一行包含研究主题的数量 M_i 那个实验室 i 正在处理。
- 第二行包含 M_i 字符串 W_{i,1}, W_{i,2}, \ldots, W_{i,M_i} 代表实验室的研究主题 i,用空格分隔。
输出
在一行中输出“有资格合作”的实验室对的数量。
示例输入 1
3 2 3 ai ml data 4 ml data web security 2 ai ml
示例输出 1
2
示例输入 2
4 1 3 biology chemistry physics 2 chemistry medicine 4 physics math statistics chemistry 3 biology ecology environment
示例输出 2
4
示例输入 3
5 3 5 deeplearning nlp vision robotics optimization 4 nlp vision speech recognition 6 deeplearning nlp vision gan transformer diffusion 3 robotics control automation 5 nlp vision deeplearning bert attention
示例输出 3
3