Q. Peace of bzjd

Codeforces

IDCFQ

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it ! The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105) Print the original string. ## Input The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105) ## Output Print the original string. [samples]

*简易版与困难版的唯一区别在于 $n$ 的约束。* Gunga 在他的数据结构课上刚学到了双端队列。双端队列（deque）是一种抽象数据类型，它推广了队列，允许元素从两端（头部或尾部）添加或删除。现在，他正在玩自己的双端队列。他有一个空的双端队列 $B$ 和一个整数数组 $A$。在第 $i$ 步操作中，他会将 $A_i$ 添加到 $B$ 的某一端。这次，他希望求出在所有 $2^n$ 种可能形成的 $B$ 中，$B_L$ 到 $B_R$ 的元素和的总和。由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果。两个队列被视为不同，当且仅当 Gunga 对某个 $A_i$ 的操作不同。第一行包含三个整数 $n, L, R$ $(1 \leq n \leq 5 \times 10^3, 1 \leq L \leq R \leq n)$ —— 整数个数和 Gunga 的感兴趣区间。第二行包含 $n$ 个空格分隔的整数 $A_1, A_2, \dots, A_n$ $(-10^9 \leq A_i \leq 10^9)$。输出一个整数，表示答案对 $10^9 + 7$ 取模的结果。在第一个例子中，无论 Gunga 将数字添加到队列的哪一端，最终队列都是 $[ 1, 1, 1, 1, 1 ]$。总和为 $32 \times (1 + 1 + 1 + 1 + 1) = 160$。在第二个例子中，有 $8$ 种可能的队列 $B$：$[ 1, 2, 3 ], [ 1, 2, 3 ], [ 2, 1, 3 ], [ 2, 1, 3 ], [ 3, 2, 1 ], [ 3, 2, 1 ], [ 3, 1, 2 ], [ 3, 1, 2 ]$。 $B_1$ 到 $B_2$ 的和的总和为 $2 \times (1 + 2 + 2 + 1 + 3 + 2 + 3 + 1) = 30$。 ## Input 第一行包含三个整数 $n, L, R$ $(1 \leq n \leq 5 \times 10^3, 1 \leq L \leq R \leq n)$ —— 整数个数和 Gunga 的感兴趣区间。第二行包含 $n$ 个空格分隔的整数 $A_1, A_2, \dots, A_n$ $(-10^9 \leq A_i \leq 10^9)$。 ## Output 输出一个整数，表示答案对 $10^9 + 7$ 取模的结果。 [samples] ## Note 在第一个例子中，无论 Gunga 将数字添加到队列的哪一端，最终队列都是 $[ 1, 1, 1, 1, 1 ]$。总和为 $32 \times (1 + 1 + 1 + 1 + 1) = 160$。在第二个例子中，有 $8$ 种可能的队列 $B$：$[ 1, 2, 3 ], [ 1, 2, 3 ], [ 2, 1, 3 ], [ 2, 1, 3 ], [ 3, 2, 1 ], [ 3, 2, 1 ], [ 3, 1, 2 ], [ 3, 1, 2 ]$。$B_1$ 到 $B_2$ 的和的总和为 $2 \times (1 + 2 + 2 + 1 + 3 + 2 + 3 + 1) = 30$。

**Definitions** Let $ n, L, R \in \mathbb{Z} $ with $ 1 \leq L \leq R \leq n $. Let $ A = (A_1, A_2, \dots, A_n) $ be a sequence of integers. Let $ \mathcal{B} $ be the set of all $ 2^n $ possible double-ended queues (deques) formed by sequentially inserting each $ A_i $ at either the front or back of an initially empty deque $ B $. **Constraints** 1. $ 1 \leq n \leq 5 \times 10^3 $ 2. $ 1 \leq L \leq R \leq n $ 3. $ -10^9 \leq A_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute $$ \sum_{B \in \mathcal{B}} \sum_{j=L}^{R} B_j \mod (10^9 + 7) $$ where $ B_j $ denotes the element at position $ j $ (1-indexed) in deque $ B $.

API Response (JSON)

{
  "problem": {
    "name": "Q. Peace of bzjd",
    "description": {
      "content": "You are given an encrypted string, encrypted using a certain algorithm. Decrypt it ! The first and single line of input contains a string s, which each of it's characters is a lower case English lett",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CFQ"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !\n\nThe first and single line of input contains a string s, which each of it's characters is a lower case English lett...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "*简易版与困难版的唯一区别在于 $n$ 的约束。*\n\nGunga 在他的数据结构课上刚学到了双端队列。双端队列（deque）是一种抽象数据类型，它推广了队列，允许元素从两端（头部或尾部）添加或删除。\n\n现在，他正在玩自己的双端队列。他有一个空的双端队列 $B$ 和一个整数数组 $A$。在第 $i$ 步操作中，他会将 $A_i$ 添加到 $B$ 的某一端。这次，他希望求出在所有 $2^n$ 种可能形...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, L, R \\in \\mathbb{Z} $ with $ 1 \\leq L \\leq R \\leq n $.  \nLet $ A = (A_1, A_2, \\dots, A_n) $ be a sequence of integers.  \nLet $ \\mathcal{B} $ be the set of all $ 2^n $ possib...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments