問題一覧 > 通常問題

No.619 CardShuffle

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 41
作問者 : くれちー / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 2029 / 自分の提出
問題文最終更新日: 2026-06-25 07:52:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2017 (順位表) の他の問題:
Advent Calendar Contest Advent Calendar 2017 Day 19 problem.

Problem Statement

December has passed its halfway point, and Y-kun seems to be preparing Christmas cards.

You are given a sequence of $N$ cards $C_1, C_2, \dots, C_N$, each with one of 0 1 2 3 4 5 6 7 8 9 + * written on it. All cards are classified into two types: operator cards, on which + or * is written, and digit cards, which are all the others. $C_1, C_N$ are digit cards, and digit cards and operator cards alternate one by one.

Regarding digit cards as single-digit integers, the operator card + as addition, and * as multiplication, let $f(X, Y)$ be the value of the expression formed by the card sequence $C_X, C_{X+1}, \dots, C_Y$. For example, when $C_1 =$ 5, $C_2 =$ +, $C_3 =$ 7, $C_4 =$ *, $C_5 =$ 4, $C_6 =$ +, $C_7 =$ 1, we have $f(1, 5) = 5 + 7 \times 4 = 5 + 28 = 33$ and $f(5, 7) = 4 + 1 = 5$.

You are given $Q$ queries of the following two types. Process them in order.

  • Swap query: swap the cards $C_X$ and $C_Y$ of the same type.
  • Question query: output $f(X, Y) \bmod (10 ^ 9 + 7)$.

Input

$N$
$C_1$ $C_2$ $\dots$ $C_N$
$Q$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$\vdots$
$T_Q$ $X_Q$ $Y_Q$

All numbers are integers. The following constraints are satisfied.

  • $3 \le N \le 10^5-1$
  • $N$ is odd
  • If $i$ is odd, then $C_i \in \{$ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 $\}$
  • If $i$ is even, then $C_i \in \{$ +, * $\}$
  • $1 \le Q \le 10^5$
  • If $i \ne Q$, then $T_i \in \{$ !, ? $\}$
  • $T_Q =$ ?
  • $1 \le X_i \lt Y_i \le N$
  • When $T_i =$ !, this represents a swap query, and
    • the cards $C_{X_i}$ and $C_{Y_i}$ are of the same type (that is, $X_i \equiv Y_i \pmod{2}$)
  • When $T_i =$ ?, this represents a question query, and
    • $X_i, Y_i$ are odd

Output

For every question query, output the answer on one line, and print a newline at the end.

Sample

Sample 1
Input
7
5 + 7 * 4 + 1
6
? 1 5
? 5 7
! 2 4
? 1 5
! 3 7
? 1 7
Output
33
5
39
16

This is the example from the problem statement.

  1. 5 + 7 * 4 + 1
  2. $f(1, 5) = 5 + 7 \times 4 = 33$
  3. $f(5, 7) = 4 + 1 = 5$
  4. 5 * 7 + 4 + 1
  5. $f(1, 5) = 5 \times 7 + 4 = 39$
  6. 5 * 1 + 4 + 7
  7. $f(1, 7) = 5 \times 1 + 4 + 7 = 16$

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。