def main():

    n = input()

    Q = 0

    AQ = [i for i in n if i == 'A' or i == 'Q']

    for i, x in enumerate(AQ):

        if x == 'A':

            lq, rq = 0, 0

            for j in range(i):

                if AQ[j] == 'Q':

                    lq += 1

            for k in range(i + 1, len(AQ)):

                if AQ[k] == 'Q':

                    rq += 1

            Q += lq * rq

    print(Q)

main()

從程式來看時間複雜度是n*n，每遇到A的話，都會往左到底、往右到底，但這樣發現會有多次計算重複。

要加速的話需要另外開兩個list，left_Q，right_Q，分別算各index當下，左邊有幾個Q、右邊有幾個Q，這邊用到DP(動態規劃的概念)。

實作：設定一個變數Q_N=0，從左邊開始讀，left_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

同樣右邊一個變數Q_N=0，從右邊開始讀，right_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

舉例QQAQ

左邊開始讀 ，
left_Q[0]=0，Q_N++

left_Q[1]=1，Q_N++

left_Q[2]=2

left_Q[3]=2，Q_N++

右邊開始讀

right_Q[3]=0，Q_N++

right_Q[2]=1，Q_N++

right_Q[1]=1

right_Q[0]=2，Q_N++

之後再遍歷字串，遇到A的時候，從index查表，取得left_Q、right_Q的值相乘、累加就是答案

def main():

    n = input()

    Q = 0

    AQ = [i for i in n if i == 'A' or i == 'Q']

    for i, x in enumerate(AQ):

        if x == 'A':

            lq, rq = 0, 0

            for j in range(i):

                if AQ[j] == 'Q':

                    lq += 1

            for k in range(i + 1, len(AQ)):

                if AQ[k] == 'Q':

                    rq += 1

            Q += lq * rq

    print(Q)

main()

從程式來看時間複雜度是n*n，每遇到A的話，都會往左到底、往右到底，但這樣發現會有多次計算重複。

要加速的話需要另外開兩個list，left_Q，right_Q，分別算各index當下，左邊有幾個Q、右邊有幾個Q，這邊用到DP(動態規劃的概念)。

實作：設定一個變數Q_N=0，從左邊開始讀，left_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

同樣右邊一個變數Q_N=0，從右邊開始讀，right_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

舉例QQAQ

左邊開始讀 ，
left_Q[0]=0，Q_N++

left_Q[1]=1，Q_N++

left_Q[2]=2

left_Q[3]=2，Q_N++

右邊開始讀

right_Q[3]=0，Q_N++

right_Q[2]=1，Q_N++

right_Q[1]=1

right_Q[0]=2，Q_N++

之後再遍歷字串，遇到A的時候，從index查表，取得left_Q、right_Q的值相乘、累加就是答案