codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1280A.md (4011B)


      1 Source: https://codeforces.com/problemset/problem/1280/A
      2 
      3 A. Cut and Paste
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 We start with a string $s$ consisting only of the digits $1$, $2$, or $3$. The length of $s$ is denoted by $|s|$. For each $i$ from $1$ to $|s|$, the $i$-th character of $s$ is denoted by $s_i$.
     22 
     23 There is one cursor. The cursor's location $\ell$ is denoted by an integer in $\{0, \ldots, |s|\}$, with the following meaning:
     24 
     25 * If $\ell = 0$, then the cursor is located before the first character of $s$.
     26 * If $\ell = |s|$, then the cursor is located right after the last character of $s$.
     27 * If $0 \lt \ell \lt |s|$, then the cursor is located between $s_\ell$ and $s_{\ell+1}$.
     28 
     29 We denote by $s_\text{left}$ the string to the left of the cursor and $s_\text{right}$ the string to the right of the cursor.
     30 
     31 We also have a string $c$, which we call our clipboard, which starts out as empty. There are three types of actions:
     32 
     33 * The Move action. Move the cursor one step to the right. This increments $\ell$ once.
     34 * The Cut action. Set $c \leftarrow s_\text{right}$, then set $s \leftarrow s_\text{left}$.
     35 * The Paste action. Append the value of $c$ to the end of the string $s$. Note that this doesn't modify $c$.
     36 
     37 The cursor initially starts at $\ell = 0$. Then, we perform the following procedure:
     38 
     39 1. Perform the Move action once.
     40 2. Perform the Cut action once.
     41 3. Perform the Paste action $s_\ell$ times.
     42 4. If $\ell = x$, stop. Otherwise, return to step 1.
     43 
     44 You're given the initial string $s$ and the integer $x$. What is the length of $s$ when the procedure stops? Since this value may be very large, only find it modulo $10^9 + 7$.
     45 
     46 It is guaranteed that $\ell \le |s|$ at any time.
     47 
     48 Input
     49 
     50 The first line of input contains a single integer $t$ ($1 \le t \le 1000$) denoting the number of test cases. The next lines contain descriptions of the test cases.
     51 
     52 The first line of each test case contains a single integer $x$ ($1 \le x \le 10^6$). The second line of each test case consists of the initial string $s$ ($1 \le |s| \le 500$). It is guaranteed, that $s$ consists of the characters "1", "2", "3".
     53 
     54 It is guaranteed that the sum of $x$ in a single file is at most $10^6$. It is guaranteed that in each test case before the procedure will stop it will be true that $\ell \le |s|$ at any time.
     55 
     56 Output
     57 
     58 For each test case, output a single line containing a single integer denoting the answer for that test case modulo $10^9 + 7$.
     59 
     60 Example
     61 
     62 Input
     63 
     64 ```
     65 4
     66 5
     67 231
     68 7
     69 2323
     70 6
     71 333
     72 24
     73 133321333
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 25
     80 1438
     81 1101
     82 686531475
     83 ```
     84 
     85 Note
     86 
     87 Let's illustrate what happens with the first test case. Initially, we have $s = $ 231. Initially, $\ell = 0$ and $c = \varepsilon$ (the empty string). The following things happen if we follow the procedure above:
     88 
     89 * Step 1, Move once: we get $\ell = 1$.
     90 * Step 2, Cut once: we get $s = $ 2 and $c = $ 31.
     91 * Step 3, Paste $s_\ell = $ 2 times: we get $s = $ 23131.
     92 * Step 4: $\ell = 1 \not= x = 5$, so we return to step 1.
     93 * Step 1, Move once: we get $\ell = 2$.
     94 * Step 2, Cut once: we get $s = $ 23 and $c = $ 131.
     95 * Step 3, Paste $s_\ell = $ 3 times: we get $s = $ 23131131131.
     96 * Step 4: $\ell = 2 \not= x = 5$, so we return to step 1.
     97 * Step 1, Move once: we get $\ell = 3$.
     98 * Step 2, Cut once: we get $s = $ 231 and $c = $ 31131131.
     99 * Step 3, Paste $s_\ell = $ 1 time: we get $s = $ 23131131131.
    100 * Step 4: $\ell = 3 \not= x = 5$, so we return to step 1.
    101 * Step 1, Move once: we get $\ell = 4$.
    102 * Step 2, Cut once: we get $s = $ 2313 and $c = $ 1131131.
    103 * Step 3, Paste $s_\ell = $ 3 times: we get $s = $ 2313113113111311311131131.
    104 * Step 4: $\ell = 4 \not= x = 5$, so we return to step 1.
    105 * Step 1, Move once: we get $\ell = 5$.
    106 * Step 2, Cut once: we get $s = $ 23131 and $c = $ 13113111311311131131.
    107 * Step 3, Paste $s_\ell = $ 1 times: we get $s = $ 2313113113111311311131131.
    108 * Step 4: $\ell = 5 = x$, so we stop.
    109 
    110 At the end of the procedure, $s$ has length $25$.