Score : $200$ points

问题描述

设有 $N$ 名参与者，编号从 $1$ 到 $N$，将参加一场包含 $M$ 道题目的比赛，题目编号从 $1$ 到 $M$。

对于整数 $i$（取值范围在 $1$ 到 $N$ 之间）和整数 $j$（取值范围在 $1$ 到 $M$ 之间），如果第 $i$ 位参与者字符串 $S_i$ 的第 $j$ 个字符为 o，则表示该参与者能解第 $j$ 题；若为 x，则表示不能解这道题。

要求参与者两人一组。请输出能够共同解决所有 $M$ 道题目的参与者配对方式的数量。

更形式化地表述，打印满足条件的整数对 $(x, y)$ 的数量，其中 $1\leq x < y\leq N$，且对于任意整数 $j$（取值范围在 $1$ 到 $M$ 之间），参与者 $x$ 和参与者 $y$ 中至少有一人能解决第 $j$ 题。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

$N$ participants, numbered $1$ to $N$, will participate in a contest with $M$ problems, numbered $1$ to $M$.

For an integer $i$ between $1$ and $N$ and an integer $j$ between $1$ and $M$, participant $i$ can solve problem $j$ if the $j$-th character of $S_i$ is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the $M$ problems.

More formally, print the number of pairs $(x,y)$ of integers satisfying $1\leq x < y\leq N$ such that for any integer $j$ between $1$ and $M$, at least one of participant $x$ and participant $y$ can solve problem $j$.

Constraints

• $N$ is an integer between $2$ and $30$, inclusive.
• $M$ is an integer between $1$ and $30$, inclusive.
• $S_i$ is a string of length $M$ consisting of o and x.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the answer.

Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants $1$ and $2$, participants $1$ and $3$, participants $1$ and $4$, participants $1$ and $5$, and participants $2$ and $3$.

On the other hand, the pair of participants $2$ and $4$, for instance, does not satisfy the condition because they cannot solve problem $4$.

Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0

update @ 2024/3/10 11:49:44