我的PAT系列文章更新重心已移至Github，歡迎來看PAT題解的小伙伴請到Github Pages瀏覽最新內(nèi)容运提。此處文章目前已更新至與Github Pages同步莫换。歡迎star我的repo咐旧。
題目
字符串 APPAPT 中包含了兩個單詞 PAT，其中第一個 PAT 是第 2 位(P)轰驳，第 4 位(A)，第 6 位(T)弟灼；第二個
PAT 是第 3 位(P)级解，第 4 位(A)，第 6 位(T)袜爪。
現(xiàn)給定字符串蠕趁，問一共可以形成多少個 PAT？
輸入格式：
輸入只有一行辛馆，包含一個字符串俺陋，長度不超過 ，只包含
P昙篙、A腊状、T 三種字母。
輸出格式：
在一行中輸出給定字符串中包含多少個 PAT苔可。由于結果可能比較大缴挖，只輸出對 1000000007 取余數(shù)的結果。
輸入樣例：
APPAPT
輸出樣例：
2
思路
這明明是一道數(shù)學題 焚辅。映屋。
怎么分析呢苟鸯？從前向后掃描：
- 每個A對應的PA組合數(shù)量是A之前P的數(shù)量，
- 每個T對應的PAT組合數(shù)量是T之前所有A對應的PA組合數(shù)量的累加棚点，
- 所有的PAT組合數(shù)量是所有T對應的PAT組合數(shù)量的累加
早处。。瘫析。懂砌梆？。贬循。咸包。
其實看通過率應該是很多人都會的哈。這道題屬于典型的90%時間用于思考杖虾，10%時間用于碼代碼的類型烂瘫。。亏掀。忱反。
然后證明一下這個magic number——1000000007為什么是這個數(shù)（大概等于）以及什么時候應該取模：
我們用有符號32位整型來計數(shù)，按照我代碼里的變量名：P滤愕、PA温算、PAT。
- P每次自增1间影，因此最大會達到10^5注竿，不需取模。
- PA每次累加P的值魂贬，我們來看一個比較極端的情況：
- "PAPA ... (共50000對PA) ... PA"巩割，這樣記錄PA的組合數(shù)量，就是
PA=1 + 2 + 3 + ... + 50000=2500050000付燥，就已經(jīng)大于int了宣谈，因此計算PA應該取模。 - PAT每次累加PA的值键科，因此兩個值都會比較大闻丑，必須要取模。累加之后（取模之前）的數(shù)會小于2000000013勋颖，這個值小于int的最大值2^31-1=2147483647嗦嗡，不會溢出（模取得過大就會在沒來得及取模之前就溢出了，我覺得這是關鍵）饭玲。
- 那用unsigned int呢侥祭，PA是不是不需要取模了？我覺得是的。
- 這道題是要檢查答案的矮冬，用一個素數(shù)做模應該有避免巧合答案的考慮谈宛。
寫完這個發(fā)現(xiàn)劉婼的博客 http://www.liuchuo.net/archives/573 也有相關的解釋，并且解題思路也不一樣欢伏，是累加每個A兩邊P和T的個數(shù)之積入挣。
代碼
最新代碼@github，歡迎交流
#include <stdio.h>
#define LIM 1000000007
int main()
{
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;
}
