{"problem":{"name":"A. QAQ","description":{"content":"\"QAQ\" is a word to denote an expression of crying. Imagine \"Q\" as eyes with tears and \"A\" as a mouth. Now Diamond has given Bort a string consisting of only uppercase English letters of length _n_. T","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF894A"},"statements":[{"statement_type":"Markdown","content":"\"QAQ\" is a word to denote an expression of crying. Imagine \"Q\" as eyes with tears and \"A\" as a mouth.\n\nNow Diamond has given Bort a string consisting of only uppercase English letters of length _n_. There is a great number of \"QAQ\" in the string (Diamond is so cute!).\n\n<center>![image](https://espresso.codeforces.com/e2ee63ac64a28b997d0d327ee841cea43f8fc0ed.png) illustration by 猫屋 https://twitter.com/nekoyaliu</center>Bort wants to know how many subsequences \"_QAQ_\" are in the string Diamond has given. Note that the letters \"_QAQ_\" don't have to be consecutive, but the order of letters should be exact.\n\n## Input\n\nThe only line contains a string of length _n_ (1 ≤ _n_ ≤ 100). It's guaranteed that the string only contains uppercase English letters.\n\n## Output\n\nPrint a single integer — the number of subsequences \"_QAQ_\" in the string.\n\n[samples]\n\n## Note\n\nIn the first example there are 4 subsequences \"_QAQ_\": \"_**QAQ**AQYSYIOIWIN_\", \"_**QA**QA**Q**YSYIOIWIN_\", \"_**Q**AQ**AQ**YSYIOIWIN_\", \"_QA**QAQ**YSYIOIWIN_\".","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"\"QAQ\" 是一个表示哭泣的词语。想象 \"Q\" 是流着泪的眼睛，\"A\" 是嘴巴。\n\n现在，Diamond 给了 Bort 一个仅由大写英文字母组成的、长度为 #cf_span[n] 的字符串。这个字符串中包含大量 \"QAQ\"（Diamond 真可爱！）。\n\nBort 想知道，在 Diamond 给出的字符串中有多少个子序列 \"_QAQ_\"。注意，字母 \"_QAQ_\" 不必连续，但字母的顺序必须完全一致。\n\n仅有一行，包含一个长度为 #cf_span[n] 的字符串（#cf_span[1 ≤ n ≤ 100]）。保证该字符串仅包含大写英文字母。\n\n请输出一个整数 —— 字符串中 \"_QAQ_\" 子序列的个数。\n\n在第一个例子中，有 #cf_span[4] 个 \"_QAQ_\" 子序列：\"_*QAQ*AQYSYIOIWIN_\"、\"_*QA*QA*Q*YSYIOIWIN_\"、\"_*Q*AQ*AQ*YSYIOIWIN_\"、\"_QA*QAQ*YSYIOIWIN_\"。\n\n## Input\n\n仅有一行，包含一个长度为 #cf_span[n] 的字符串（#cf_span[1 ≤ n ≤ 100]）。保证该字符串仅包含大写英文字母。\n\n## Output\n\n请输出一个整数 —— 字符串中 \"_QAQ_\" 子序列的个数。\n\n[samples]\n\n## Note\n\n在第一个例子中，有 #cf_span[4] 个 \"_QAQ_\" 子序列：\"_*QAQ*AQYSYIOIWIN_\"、\"_*QA*QA*Q*YSYIOIWIN_\"、\"_*Q*AQ*AQ*YSYIOIWIN_\"、\"_QA*QAQ*YSYIOIWIN_\".","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ s $ be a string of length $ n $, where $ s[i] \\in \\{ \\text{A}, \\text{Q}, \\dots \\} $ for $ 0 \\leq i < n $.\n\nDefine a subsequence \"QAQ\" as a triplet of indices $ (i, j, k) $ such that:\n- $ 0 \\leq i < j < k < n $,\n- $ s[i] = \\text{Q} $,\n- $ s[j] = \\text{A} $,\n- $ s[k] = \\text{Q} $.\n\nLet $ \\text{count} = \\sum_{\\substack{0 \\leq i < j < k < n \\\\ s[i] = \\text{Q},\\, s[j] = \\text{A},\\, s[k] = \\text{Q}}} 1 $.\n\nOutput $ \\text{count} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF894A","tags":["brute force","dp"],"sample_group":[["QAQAQYSYIOIWIN","4"],["QAQQQZZYNOIWIN","3"]],"created_at":"2026-03-03 11:00:39"}}