D. String Mark

Codeforces

IDCF895D

Time4000ms

Memory256MB

Difficulty—

combinatoricsmathstrings

English · Original

Chinese · Translation

Formal · Original

At the Byteland State University marks are strings of the same length. Mark _x_ is considered better than _y_ if string _y_ is lexicographically smaller than _x_. Recently at the BSU was an important test work on which Vasya recived the mark _a_. It is very hard for the teacher to remember the exact mark of every student, but he knows the mark _b_, such that every student recieved mark strictly smaller than _b_. Vasya isn't satisfied with his mark so he decided to improve it. He can swap characters in the string corresponding to his mark as many times as he like. Now he want to know only the number of different ways to improve his mark so that his teacher didn't notice something suspicious. More formally: you are given two strings _a_, _b_ of the same length and you need to figure out the number of different strings _c_ such that: 1) _c_ can be obtained from _a_ by swapping some characters, in other words _c_ is a permutation of _a_. 2) String _a_ is lexicographically smaller than _c_. 3) String _c_ is lexicographically smaller than _b_. For two strings _x_ and _y_ of the same length it is true that _x_ is lexicographically smaller than _y_ if there exists such _i_, that _x_1 = _y_1, _x_2 = _y_2, ..., _x__i_ - 1 = _y__i_ - 1, _x__i_ < _y__i_. Since the answer can be very large, you need to find answer modulo 109 + 7. ## Input First line contains string _a_, second line contains string _b_. Strings _a_, _b_ consist of lowercase English letters. Their lengths are equal and don't exceed 106. It is guaranteed that _a_ is lexicographically smaller than _b_. ## Output Print one integer — the number of different strings satisfying the condition of the problem modulo 109 + 7. [samples] ## Note In first sample from string _abc_ can be obtained strings _acb_, _bac_, _bca_, _cab_, _cba_, all of them are larger than _abc_, but smaller than _ddd_. So the answer is 5. In second sample any string obtained from _abcdef_ is larger than _abcdeg_. So the answer is 0.

在 Byteland 国立大学，成绩用相同长度的字符串表示。字符串 #cf_span[y] 在字典序上小于 #cf_span[x] 时，认为标记 #cf_span[x] 优于 #cf_span[y]。最近在 BSU 举行了一次重要考试，Vasya 得到了标记 #cf_span[a]。老师很难记住每个学生的准确成绩，但他知道一个标记 #cf_span[b]，使得所有学生的成绩都严格小于 #cf_span[b]。 Vasya 对自己的成绩不满意，因此决定改进它。他可以任意多次交换其成绩字符串中的字符。现在他想知道有多少种不同的方式可以改进他的成绩，使得老师不会察觉到异常。更正式地：给你两个长度相同的字符串 #cf_span[a] 和 #cf_span[b]，你需要计算满足以下条件的不同字符串 #cf_span[c] 的数量： 1) #cf_span[c] 可以通过交换 #cf_span[a] 中的某些字符得到，换句话说，#cf_span[c] 是 #cf_span[a] 的一个排列。 2) 字符串 #cf_span[a] 在字典序上小于 #cf_span[c]。 3) 字符串 #cf_span[c] 在字典序上小于 #cf_span[b]。对于两个长度相同的字符串 #cf_span[x] 和 #cf_span[y]，当且仅当存在某个位置 #cf_span[i]，使得 #cf_span[x_1 = y_1, x_2 = y_2, ..., x_{i-1} = y_{i-1}, x_i < y_i] 时，称 #cf_span[x] 在字典序上小于 #cf_span[y]。由于答案可能很大，你需要对 #cf_span[10^9 + 7] 取模输出。第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。字符串 #cf_span[a] 和 #cf_span[b] 由小写英文字母组成，长度相等且不超过 #cf_span[10^6]。保证 #cf_span[a] 在字典序上小于 #cf_span[b]。输出一个整数 —— 满足题目条件的不同字符串的数量，对 #cf_span[10^9 + 7] 取模。在第一个样例中，从字符串 #cf_span[abc] 可以得到字符串 #cf_span[acb, bac, bca, cab, cba]，它们都大于 #cf_span[abc] 但小于 #cf_span[ddd]。因此答案是 #cf_span[5]。在第二个样例中，任何从 #cf_span[abcdef] 得到的字符串都大于 #cf_span[abcdeg]。因此答案是 #cf_span[0]。 ## Input 第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。字符串 #cf_span[a, b] 由小写英文字母组成，长度相等且不超过 #cf_span[10^6]。保证 #cf_span[a] 在字典序上小于 #cf_span[b]。 ## Output 输出一个整数 —— 满足题目条件的不同字符串的数量，对 #cf_span[10^9 + 7] 取模。 [samples] ## Note 在第一个样例中，从字符串 #cf_span[abc] 可以得到字符串 #cf_span[acb, bac, bca, cab, cba]，它们都大于 #cf_span[abc] 但小于 #cf_span[ddd]。因此答案是 #cf_span[5]。在第二个样例中，任何从 #cf_span[abcdef] 得到的字符串都大于 #cf_span[abcdeg]。因此答案是 #cf_span[0]。

**Definitions** Let $ a, b \in \Sigma^n $ be two strings of equal length $ n $, where $ \Sigma = \{ \text{a}, \text{b}, \dots, \text{z} \} $, and $ a \prec b $ lexicographically. Let $ P(a) $ denote the set of all distinct permutations of $ a $. **Constraints** 1. $ 1 \leq n \leq 10^6 $ 2. $ a, b $ consist of lowercase English letters 3. $ a \prec b $ (lexicographically) **Objective** Compute: $$ \left| \left\{ c \in P(a) \mid a \prec c \prec b \right\} \right| \mod (10^9 + 7) $$

Samples

Input #1

abc
ddd

Output #1

Input #2

abcdef
abcdeg

Output #2

Input #3

abacaba
ubuduba

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. String Mark",
    "description": {
      "content": "At the Byteland State University marks are strings of the same length. Mark _x_ is considered better than _y_ if string _y_ is lexicographically smaller than _x_. Recently at the BSU was an important",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF895D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "At the Byteland State University marks are strings of the same length. Mark _x_ is considered better than _y_ if string _y_ is lexicographically smaller than _x_.\n\nRecently at the BSU was an important...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在 Byteland 国立大学，成绩用相同长度的字符串表示。字符串 #cf_span[y] 在字典序上小于 #cf_span[x] 时，认为标记 #cf_span[x] 优于 #cf_span[y]。\n\n最近在 BSU 举行了一次重要考试，Vasya 得到了标记 #cf_span[a]。老师很难记住每个学生的准确成绩，但他知道一个标记 #cf_span[b]，使得所有学生的成绩都严格小于 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\Sigma^n $ be two strings of equal length $ n $, where $ \\Sigma = \\{ \\text{a}, \\text{b}, \\dots, \\text{z} \\} $, and $ a \\prec b $ lexicographically.  \nLet $ P(a) $ deno...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments