← 返回题目列表

AtCoder · abc282_b

C. 让我们获得满分

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

N 参与者,编号 1 to N,将参加一场比赛 M 问题,已编号 1 to M.

对于整数 i 之间 1 和 N 和一个整数 j 之间 1 和 M,参与者 i 可以解决问题 j 如果 j- 第一个字符 S_i is o,如果该字符是则无法解决 x.

参与者必须成对出现。打印形成一对参与者的方法数,他们可以共同解决所有问题 M 问题。

更正式地说,打印对的数量 (x,y) 的整数满足 1\leq x < y\leq N 这样对于任何整数 j 之间 1 和 M,至少一名参与者 x 和参与者 y 可以解决问题 j.

约束

  • N 是介于 2 和 30,包括在内。
  • M 是介于 1 和 30,包括在内。
  • S_i 是一个长度为 M 组成 o 和 x.

输入

输入由标准输入按以下格式给出:

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