（原创不成功去参考）PTA乙级1040 有几个PAT

当时真的想了很久，第一遍代码是纯暴力解决，做之前我就知道肯定不行，运行绝对超时，没办法，这代码写起来看上去简单，哈哈哈哈
第二遍，想了想用逐步标记不同字母位置，算出其倍数来叠加次数。结果还是运算超时，因为还是存在双循环，还是没想出
第三遍，没办法，看网上各位有经验的博主贴出的代码，主流有两种，当时看到我几乎撞墙，觉得白学了一样
其实你我都知道这是数学问题，但我又不知道具体是什么数学问题，不然都想去搜索相关材料好好进修一下
最后贴出我的第二遍的代码,实在惭愧。

1040 有几个PAT （25 分）
字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。
现给定字符串，问一共可以形成多少个 PAT？
输入格式： 输入只有一行，包含一个字符串，长度不超过10的​5次方 ，只包含 P、A、T 三种字母。
输出格式：在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。
输入样例：
APPAPT
输出样例：
2

正确代码：自己再在根据理解情况下写一次

#include <stdio.h>
#define LIM 1000000007
int main()
{
    unsigned int Pcount=0,Acount=0,Tcount=0,i=0,aPos=0,PATcount=0;
    char c,str[100001];
    //1.先处理好输入 
    while((c = getchar()) != '\n')
    {
        if(c=='A')
            Acount++;
        else if(c=='T')
            Tcount++;
        str[i++] = c;
    }
    str[i]='\n';
    
    //2.计算过程，用了一种能理解方法，以A为中心，算出前后PT的次数累加
    i=0;
    while(str[i]!='\n'&&aPos<Acount) 
    {
        if(str[i]=='P')
            Pcount++;
        else if(str[i]=='A')
        //每次遇到A，应该把前后的P与T的次数相乘 ,%LIM 我是想，如果Pcount与Tcount都达到五位数极限状态，提前%LIM提防溢出 
        //当时我写成PATcount = PATcount + (Pcount*Tcount)%LIM ，一样溢出，倒置最后两个测试点过不了，
        //还是在外面在包一层%LIM才能过 
            PATcount = (PATcount + (Pcount*Tcount)%LIM)%LIM;
        else if(str[i]=='T')
            Tcount--;
        i++; 
    }
    //3.输出 
    printf("%d\n",PATcount%LIM);
    return 0; 
}

另外一个主流的解法，这是个看着似懂非懂的代码，我觉得最神就是这个代码，但还是理解不了,在输入过程中已经计算好了，神！！

#include <stdio.h>
#define LIM 1000000007
int main()
{
    unsigned int P = 0, PA = 0, PAT = 0;
    char c;
    while((c = getchar()) != '\n')
    {
        if(c == 'P')   P++;
        if(c == 'A')   PA = (PA + P) % LIM;
        if(c == 'T')   PAT = (PAT + PA) % LIM;
    }
    printf("%d", PAT);
    return 0;
}

第二遍的代码：(一开始我是以PPPAAATTT为蓝图)，后来才发觉忽略了一种情况，P位置不变，A与T相对变化的个数，再加上这种情况时候已经是多重循环。

#include <stdio.h>
int main()
{   
    int positP=0,positA=0,positT=0,lengthP,lengthA,lengthT;
    int PosP[100001],PosA[100001],PosT[100001];
    int count=0,i=0,j=0,k=0,isTerminal=0;
    char c;
    while((c=getchar())!=EOF&&c!=' '&&c!='\n')
    {
        if(c=='P')
            PosP[positP++] = i;
        else if(c=='A')
            PosA[positA++] = i;
        else if(c=='T')
            PosT[positT++] = i;
        i++;
    }
    lengthP=positP;
    lengthA=positA;
    lengthT=positT;
    
    i=j=k=0;
    
    while(i<lengthP&&j<lengthA&&k<lengthT)
    {
        
        int Tcount=0,Acount =0,Pcount = 0;
        //先找能符合A在P后面的A位置 
        for(;PosP[i]>PosA[j]&&j<lengthA;j++)
            ;
        //再找能符合T在A后面的T位置
         for(;PosA[j]>PosT[k]&&k<lengthT;k++)
            ;
        //找到之后依然符合条件的话
        //1.P与A 位置不变，看看有多少个T符合 
        if(i<lengthP&&j<lengthA&&k<lengthT)
        {
            //看看T后面有多少个直接加进来 
            Tcount = lengthT - k;
            Acount = 1;
            Pcount = 1;
        }
        else
            break;
            
        //2.
        int preApos = j;
        int preTpos = k;
        //2.2 P位置不变，T与A相对变化，看看有多少个符合 
        while(j<lengthA&&k<lengthT)
        {
            //要找到A在T后面的首个A位置 
            for(;PosA[j]<PosT[k]&&j<lengthA;j++)
                ;
            if(j<lengthA)
            {
                //再要找到T在A后面的T位置 
                for(;PosA[j]>PosT[k]&&k<lengthT;k++)
                    ;
                if(k<lengthT)
                {
                    //看看T后面有多少个直接加进来 
                    count+=lengthT - k;
                }
            }
        }
        //2.1 P与T位置不变化，看看有多少个A符合 
        j=preApos;
        k=preTpos;
        while(PosA[++j]<PosT[k]&&j<lengthA)
            Acount++;
        
        
        j=preApos;
        k=preTpos;
        //3.A与T位置不变，看看有多少个P符合
        int prePpos = i; 
        while(PosP[++i]<PosA[j]&&i<lengthP)
        {
            Pcount++;
            prePpos = i;
        }
            
        i=prePpos;
        count+=Tcount*Acount*Pcount;
        i++;
    }
    printf("%d\n",count%1000000007);
    return 0;
}