题目

The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT’s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 10 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT’s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

1

APPAPT

Sample Output:

1

2

分析

对每个A来说能组成的PAT数等于左边P的数量乘右边T的数量。

这是第一次写题卡在神奇的1000000007上过不去，傻乎乎的做完所有运算printf前再取模。

搜了一下发现1000000007另有玄机。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char input[100001];
int leftP[100001];
int rightT[100001];

int main()
{
    int len;
    int total=0;
    scanf("%s",input);
    len = strlen(input);
    if(input[0]=='P') leftP[0]=1;
    if(input[len-1]=='T') rightT[len-1]=1;
    for(int i=1;i<len;i++)
        if(input[i]=='P')
            leftP[i]=leftP[i-1]+1;
        else
            leftP[i]=leftP[i-1];

    for(int i=len-1;i>0;i--)
    {
        if(input[i-1]=='T')
            rightT[i-1]=rightT[i]+1;
        else
            rightT[i-1]=rightT[i];
        if(input[i]=='A')
            total = (total+rightT[i]*leftP[i])%1000000007;
    }
    printf("%d",total);

    return 0;
}

为什么要对1000000007取模

大数阶乘，大数的排列组合等，一般都要求将输出结果对1000000007取模 为什么总是1000000007呢= = 大概≖‿≖✧是因为：（我猜的，不服你打我呀~） 1. 1000000007是一个质数 2. int32位的最大值为2147483647，所以对于int32位来说1000000007足够大 3. int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出 所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出 ｡◕‿◕｡

原文：https://www.liuchuo.net/archives/645