#P18263. Looping RPS
Looping RPS
Looping RPS
本题用 K 表示石头,P 表示布,N 表示剪刀,分别取自相应波兰语单词的首字母。布胜石头,石头胜剪刀,剪刀胜布。
两名选手对决时同时出招。如果手势不同,立即根据上述规则分出胜负;如果相同,就继续出下一招。如果两人始终出相同手势,这场对决永远不会结束,视为平局。
在今天的比赛中,每名选手预先写下一个由 K、P、N 组成的非空策略串。每次开始对决时,都从策略串的第一个字符开始,并无限循环使用整个串。 例如,KPP 表示依次出石头、布、布、石头、布、布,依此类推。
共有 名选手,第 名的策略为 。组织者希望找出能够像石头、剪刀、布一样互相克制的三名选手:将他们适当排列为 后, 胜 、 胜 、 胜 。
求满足条件的无序三元组数量。三元组中的选手必须互不相同;策略串相同的选手仍然是不同的人。
输入格式
第一行包含一个整数 。
接下来 行,每行包含一个非空字符串 ,只由 K、P、N 组成。
输出格式
输出一个整数,表示满足条件的无序三元组数量。
数据范围
- ;
- 所有策略串的总长度不超过 ;
- 输入只有一组数据。
样例
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,因此形成循环克制。