codeforces-scrape

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

2025B.md (1597B)


      1 Source: https://codeforces.com/problemset/problem/2025/B
      2 
      3 B. Binomial Coefficients, Kind Of
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Recently, akshiM met a task that needed binomial coefficients to solve. He wrote a code he usually does that looked like this:
     22 
     23 ```
     24     for (int n = 0; n < N; n++) { // loop over n from 0 to N-1 (inclusive)  
     25         C[n][0] = 1;  
     26         C[n][n] = 1;  
     27         for (int k = 1; k < n; k++) // loop over k from 1 to n-1 (inclusive)  
     28             C[n][k] = C[n][k - 1] + C[n - 1][k - 1];  
     29     }
     30 ```
     31 
     32 Unfortunately, he made an error, since the right formula is the following:
     33 
     34 ```
     35             C[n][k] = C[n - 1][k] + C[n - 1][k - 1]
     36 ```
     37 
     38 But his team member keblidA is interested in values that were produced using the wrong formula. Please help him to calculate these coefficients for $t$ various pairs $(n_i, k_i)$. Note that they should be calculated according to the first (wrong) formula.
     39 
     40 Since values $C[n_i][k_i]$ may be too large, print them modulo $10^9 + 7$.
     41 
     42 Input
     43 
     44 The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of pairs. Next, $t$ pairs are written in two lines.
     45 
     46 The second line contains $t$ integers $n_1, n_2, \dots, n_t$ ($2 \le n_i \le 10^5$).
     47 
     48 The third line contains $t$ integers $k_1, k_2, \dots, k_t$ ($1 \le k_i \lt n_i$).
     49 
     50 Output
     51 
     52 Print $t$ integers $C[n_i][k_i]$ modulo $10^9 + 7$.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 7
     60 
     61 2 5 5 100000 100000 100000 100000
     62 
     63 1 2 3 1 33333 66666 99999
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 2
     70 4
     71 8
     72 2
     73 326186014
     74 984426998
     75 303861760
     76 ```