K. Palindromes Building

Codeforces

IDCF10153K

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

An _anagram_ is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once, such as "_post_", "_stop_", and "_spot_". You are given a string s consisting of lowercase English letters. Your task is to count how many distinct anagrams of the string s are palindromes. A _palindrome_ is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "_madam_" or "_racecar_". For example, "_aabb_" has 6 distinct anagrams, which are: "_aabb_", "_abab_", "_abba_", "_baab_", "_baba_", "_bbaa_". Two of the previous anagrams are palindromes, which are: "_abba_", "_baab_". The first line contains an integer T, where T is the number of test cases. The first line of each test case contains an integer n (1 ≤ n ≤ 20), where n is the length of the string s. The second line of each test contains a string s of length n consisting of lowercase English letters. For each test case, print a single line containing how many distinct anagrams of the string s are palindromes. ## Input The first line contains an integer T, where T is the number of test cases.The first line of each test case contains an integer n (1 ≤ n ≤ 20), where n is the length of the string s.The second line of each test contains a string s of length n consisting of lowercase English letters. ## Output For each test case, print a single line containing how many distinct anagrams of the string s are palindromes. [samples]

**Definitions** Let $ T \in \mathbb{Z}^+ $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $, $ 1 \leq n_k \leq 20 $, be the length of string $ s_k $. - Let $ s_k \in \Sigma^{n_k} $, where $ \Sigma = \{a, b, \dots, z\} $, be the input string. Let $ f_k : \Sigma \to \mathbb{Z}_{\geq 0} $ denote the frequency count of each character in $ s_k $, i.e., $ f_k(c) = |\{i : s_k[i] = c\}| $. **Constraints** 1. $ 1 \leq T \leq \text{unspecified (but finite)} $ 2. For each $ k $: $ 1 \leq n_k \leq 20 $, and $ s_k $ consists only of lowercase English letters. **Objective** For each test case $ k $, compute the number of distinct palindromic anagrams of $ s_k $. A string is a palindromic anagram of $ s_k $ if: - It is a permutation of $ s_k $, and - It reads the same forwards and backwards. Such a palindrome exists **iff** at most one character in $ s_k $ has odd frequency. If this condition holds, the number of distinct palindromic anagrams is: $$ \frac{\left( \left\lfloor \frac{n_k}{2} \right\rfloor \right)!}{\prod_{c \in \Sigma} \left( \left\lfloor \frac{f_k(c)}{2} \right\rfloor \right)!} $$ Otherwise, the count is $ 0 $.

API Response (JSON)

{
  "problem": {
    "name": "K. Palindromes Building",
    "description": {
      "content": "An _anagram_ is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once, such as \"_post_\", \"_stop_\", and \"_spot_\". You are given a st",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10153K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "An _anagram_ is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once, such as \"_post_\", \"_stop_\", and \"_spot_\".\n\nYou are given a st...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $, $ 1 \\leq n_k \\leq 20 $, be the length of strin...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments