#P18263. Looping RPS

Looping RPS

Looping RPS

本题用 K 表示石头,P 表示布,N 表示剪刀,分别取自相应波兰语单词的首字母。布胜石头,石头胜剪刀,剪刀胜布。

两名选手对决时同时出招。如果手势不同,立即根据上述规则分出胜负;如果相同,就继续出下一招。如果两人始终出相同手势,这场对决永远不会结束,视为平局。

在今天的比赛中,每名选手预先写下一个由 K、P、N 组成的非空策略串。每次开始对决时,都从策略串的第一个字符开始,并无限循环使用整个串。 例如,KPP 表示依次出石头、布、布、石头、布、布,依此类推。

共有 nn 名选手,第 ii 名的策略为 sis_i。组织者希望找出能够像石头、剪刀、布一样互相克制的三名选手:将他们适当排列为 (A,B,C)(A,B,C) 后,AA 胜 BB、BB 胜 CC、CC 胜 AA。

求满足条件的无序三元组数量。三元组中的选手必须互不相同;策略串相同的选手仍然是不同的人。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,每行包含一个非空字符串 sis_i,只由 K、P、N 组成。

输出格式

输出一个整数,表示满足条件的无序三元组数量。

数据范围

  • 3≤n≤1053\le n\le10^5;
  • 所有策略串的总长度不超过 10610^6;
  • 输入只有一组数据。

样例

6
P
PN
KK
N
PKK
PN
6

样例解释

用 PN′ 表示第二个策略串为 PN 的选手,六个满足条件的三元组为:

  • (P, KK, N);
  • (P, PKK, PN);
  • (P, PKK, PN′);
  • (PN, KK, N);
  • (KK, N, PKK);
  • (KK, N, PN′)。

例如,第二个三元组中,P 在第二招用布战胜 PKK 的石头;PKK 战胜 PN;PN 战胜 P,因此形成循环克制。