Will and Closed Set
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Will Hunting was learning about Greatest Common Divisor (gcd) of two numbers and properties related to it. He came across the concept of a closed set. He learned that a set is said to be closed under some operation iff for any two elements in the set, the result obtained after applying the operation on those two elements is also a part of the set.
Professor Lambeau wants to test Will on this newly learned topic. He comes up with the following challenge for Will. Consider an array A of length N. The array may or may not be closed under some operation. He wants to add exactly K elements in the array in the range [1, L] such that the resulting array is closed under the gcd operation. Note that the order in which the elements are going to be added does not matter. Also, an array B will be called closed under gcd operation, if for any two indices i, j, the element gcd(Bi, Bj) is also present in the array.
Will has started thinking about this problem. Can you beat him to the task and compute the number of ways before he does? Note that the answer could be large, so you must report it modulo 109 + 7.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
For each test case, first line consists three space separated integers denoting N, K, L.
Second line of each test case, contains N space separated integers denoting array A.
For each test case, output a single line containing an integer corresponding to the number of ways of adding elements in the range [1, L] to make the array closed under gcd operation.
- 1 ≤ T ≤ 10
- 1 ≤ N, Ai, K, L ≤ 27
- There exists an i such that Ai = 1
- Maximum value in the array A ≤ L
SubtasksSubtask #1 (40 points), Time limit : 4 secs
- 1 ≤ N, Ai, K, L ≤ 15
- 1 ≤ N, Ai, K, L ≤ 25
- 1 ≤ N, Ai, K, L ≤ 27
Input: 2 2 1 2 2 1 3 1 6 1 4 6 Output: 2 1
In Test 1 : The array A = [2, 1]. The array is already closed under gcd operation since gcd(2, 2) = 2, gcd(1, 1) = 1 and gcd(2, 1) = 2. So, the remaining element which needs to be added can be either 1 or 2. So, answer is 2.
In Test 2 : The array A = [1, 4, 6]. gcd(1, 1), gcd(1, 4) and gcd(1, 6) = 1 which is present in the array. gcd(4, 6) is 2 which is not present in the array. We have to add only one element in the array and make it closed under gcd operation. So the number to be added can only be 2. There is only one way of doing that. So, the answer is 1.
|Tags||admin2, dp+bitmask, dynamic-programming, hard, ltime38|
|Time Limit:||2 - 4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.