A. Aramic script

Codeforces

IDCF975A

Time1000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

In Aramic language words can only represent objects. Words in Aramic have special properties: * A word is a _root_ if it does not contain the same letter more than once. * A _root_ and all its permutations represent the same object. * The _root_ $x$ of a word $y$ is the word that contains all letters that appear in $y$ in a way that each letter appears once. For example, the _root_ of "_aaaa_", "_aa_", "_aaa_" is "_a_", the _root_ of "_aabb_", "_bab_", "_baabb_", "_ab_" is "_ab_". * Any word in Aramic represents the same object as its _root_. You have an ancient script in Aramic. What is the number of **different objects** mentioned in the script? ## Input The first line contains one integer $n$ ($1 \leq n \leq 10^3$) — the number of words in the script. The second line contains $n$ words $s_1, s_2, \ldots, s_n$ — the script itself. The length of each string does not exceed $10^3$. It is guaranteed that all characters of the strings are small latin letters. ## Output Output one integer — the number of different objects mentioned in the given ancient Aramic script. [samples] ## Note In the first test, there are two objects mentioned. The roots that represent them are "_a_","_ab_". In the second test, there is only one object, its root is "_amer_", the other strings are just permutations of "_amer_".

在阿兰语中，单词只能表示物体。阿兰语的单词具有特殊性质：你有一份古老的阿兰语手稿。手稿中提到了多少个*不同的物体*？第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^3$) —— 手稿中的单词数量。第二行包含 $n$ 个单词 $s_1, s_2, dots.h, s_n$ —— 手稿本身。每个字符串的长度不超过 $10^3$。保证所有字符串中的字符均为小写拉丁字母。请输出一个整数 —— 给定的古老阿兰语手稿中提到的不同物体的数量。在第一个测试用例中，提到了两个物体。表示它们的词根是 "_a_"、"_ab_"。在第二个测试用例中，只有一个物体，其词根是 "_amer_"，其他字符串只是 "_amer_" 的排列。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^3$) —— 手稿中的单词数量。第二行包含 $n$ 个单词 $s_1, s_2, dots.h, s_n$ —— 手稿本身。每个字符串的长度不超过 $10^3$。保证所有字符串中的字符均为小写拉丁字母。 ## Output 请输出一个整数 —— 给定的古老阿兰语手稿中提到的不同物体的数量。 [samples] ## Note 在第一个测试用例中，提到了两个物体。表示它们的词根是 "_a_"、"_ab_"。在第二个测试用例中，只有一个物体，其词根是 "_amer_"，其他字符串只是 "_amer_" 的排列。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of words in the script. Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence of strings, where each $ s_i $ consists of lowercase Latin letters. For any string $ s $, define its *root* as the set of distinct characters in $ s $, represented as a sorted string (or equivalently, as a set). Let $ R(s) = \text{sorted}(\text{set}(s)) $ denote the root of string $ s $. **Constraints** 1. $ 1 \le n \le 10^3 $ 2. For each $ i \in \{1, \dots, n\} $, $ 1 \le |s_i| \le 10^3 $ 3. Each character in every $ s_i $ is a lowercase Latin letter. **Objective** Compute the number of distinct roots among all words in the script: $$ \left| \left\{ R(s_i) \mid i \in \{1, \dots, n\} \right\} \right| $$

Samples

Input #1

5
a aa aaa ab abb

Output #1

Input #2

3
amer arem mrea

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Aramic script",
    "description": {
      "content": "In Aramic language words can only represent objects. Words in Aramic have special properties: *   A word is a _root_ if it does not contain the same letter more than once. *   A _root_ and all its p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF975A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In Aramic language words can only represent objects.\n\nWords in Aramic have special properties:\n\n*   A word is a _root_ if it does not contain the same letter more than once.\n*   A _root_ and all its p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在阿兰语中，单词只能表示物体。\n\n阿兰语的单词具有特殊性质：\n\n你有一份古老的阿兰语手稿。手稿中提到了多少个*不同的物体*？\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^3$) —— 手稿中的单词数量。\n\n第二行包含 $n$ 个单词 $s_1, s_2, dots.h, s_n$ —— 手稿本身。每个字符串的长度不超过 $10^3$。\n\n保证所有字符串中的字符均为小写拉...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of words in the script.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence of strings, where each $ s_i $ consists of lowercase Latin letters.\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments