codeforces-scrape

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

595B.md (2353B)


      1 Source: https://codeforces.com/problemset/problem/595/B
      2 
      3 B. Pasha and Phone
      4 
      5 time limit per test
      6 
      7 1 second
      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 Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly *n* digits.
     22 
     23 Also Pasha has a number *k* and two sequences of length *n* / *k* (*n* is divisible by *k*) *a*1, *a*2, ..., *a**n* / *k* and *b*1, *b*2, ..., *b**n* / *k*. Let's split the phone number into blocks of length *k*. The first block will be formed by digits from the phone number that are on positions 1, 2,..., *k*, the second block will be formed by digits from the phone number that are on positions *k* + 1, *k* + 2, ..., 2·*k* and so on. Pasha considers a phone number good, if the *i*-th block doesn't start from the digit *b**i* and is divisible by *a**i* if represented as an integer.
     24 
     25 To represent the block of length *k* as an integer, let's write it out as a sequence *c*1, *c*2,...,*c**k*. Then the integer is calculated as the result of the expression *c*1·10*k* - 1 + *c*2·10*k* - 2 + ... + *c**k*.
     26 
     27 Pasha asks you to calculate the number of good phone numbers of length *n*, for the given *k*, *a**i* and *b**i*. As this number can be too big, print it modulo 109 + 7.
     28 
     29 Input
     30 
     31 The first line of the input contains two integers *n* and *k* (1 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ *min*(*n*, 9)) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that *n* is divisible by *k*.
     32 
     33 The second line of the input contains *n* / *k* space-separated positive integers — sequence *a*1, *a*2, ..., *a**n* / *k* (1 ≤ *a**i* < 10*k*).
     34 
     35 The third line of the input contains *n* / *k* space-separated positive integers — sequence *b*1, *b*2, ..., *b**n* / *k* (0 ≤ *b**i* ≤ 9).
     36 
     37 Output
     38 
     39 Print a single integer — the number of good phone numbers of length *n* modulo 109 + 7.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 6 2  
     47 38 56 49  
     48 7 3 4
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 8
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 8 2  
     61 1 22 3 44  
     62 5 4 3 2
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 32400
     69 ```
     70 
     71 Note
     72 
     73 In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.