pat 1093

1、题目链接

https://www.patest.cn/contests/pat-a-practise/1093

2、题意分析

（1）题意：分析一个字符串中拥有多少个不重复的PAT

（2）分析：有两种思路。

1）我们可以从头到尾依次遍历一个字符串，如果当前字符等于P，则再从当前位置遍历，找出字符A，然后再在字符A的基础上找出字符T，累计这样的次数，最后取余，得到最后的一个答案。

2）同时，我们可以找出这个字符串中每个A前面有多少个P，后面有多少个T。根据排列与组合原理，可知每个字母A可以组成的PAT有sumP*sumT个，然后将这些sumP*sumT累加，然后取余，得到答案。

3、第一种方法代码如下：

但是上交测试之后发现时间超过，因为我们使用了三次循环，导致时间超过，所以这里推荐使用第二种方法，代码如下：