888D.md (945B)
1 Source: https://codeforces.com/problemset/problem/888/D 2 3 D. Almost Identity Permutations 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 A permutation *p* of size *n* is an array such that every integer from 1 to *n* occurs exactly once in this array. 22 23 Let's call a permutation an almost identity permutation iff there exist at least *n* - *k* indices *i* (1 ≤ *i* ≤ *n*) such that *p**i* = *i*. 24 25 Your task is to count the number of almost identity permutations for given numbers *n* and *k*. 26 27 Input 28 29 The first line contains two integers *n* and *k* (4 ≤ *n* ≤ 1000, 1 ≤ *k* ≤ 4). 30 31 Output 32 33 Print the number of almost identity permutations for given *n* and *k*. 34 35 Examples 36 37 Input 38 39 ``` 40 4 1 41 ``` 42 43 Output 44 45 ``` 46 1 47 ``` 48 49 Input 50 51 ``` 52 4 2 53 ``` 54 55 Output 56 57 ``` 58 7 59 ``` 60 61 Input 62 63 ``` 64 5 3 65 ``` 66 67 Output 68 69 ``` 70 31 71 ``` 72 73 Input 74 75 ``` 76 5 4 77 ``` 78 79 Output 80 81 ``` 82 76 83 ```