102821: [AtCoder]ABC282 B - Let's Get a Perfect Score

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

问题描述

编号为$1$到$N$的$N$名选手将参加一个包含$M$个问题的比赛，问题编号为$1$到$M$。

对于$1$到$N$之间的整数$i$和$1$到$M$之间的整数$j$，如果$S_i$的第$j$个字符为o，选手$i$可以解决问题$j$，如果该字符为x，则不能解决该问题。

选手必须成对参加。打印能够共同解决所有$M$个问题的选手配对方式的数量。

更正式地说，打印满足$1\leq x < y\leq N$的整数对$(x,y)$的数量，使得对于$1$到$M$之间的任意整数$j$，选手$x$和选手$y$中至少有一人能够解决问题$j$。

约束

• $N$是一个介于$2$和$30$之间的整数。
• $M$是一个介于$1$和$30$之间的整数。
• $S_i$是一个由o和x组成的长度为$M$的字符串。

输入

输入从标准输入以以下格式给出：

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

打印答案。

样例输入 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

样例输出 1

5

满足条件的五对选手是：选手$1$和$2$，选手$1$和$3$，选手$1$和$4$，选手$1$和$5$，以及选手$2$和$3$。

另一方面，选手$2$和$4$的组合不满足条件，因为他们不能解决问题$4$。

样例输入 2

3 2
ox
xo
xx

样例输出 2

1

样例输入 3

2 4
xxxx
oxox

样例输出 3

0