PROBLEM LINK:Author: Sergey Nagin DIFFICULTY:MEDIUMHARD PREREQUISITES:Solving Dynamic Programming with Matrix Expo PROBLEM:In this problem Sereja is interested in number of arrays A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ M, A[i]  integer) such that least common multiple (LCM) of all its elements is divisible by number D. Please, find sum of answers to the problem with D = L, D = L+1, ..., D = R. As answer could be large, please output it modulo (10^{9} + 7). TECHNIQUE:I will suggest to specifically read the whole post given in prerequisite if you are not aware about this technique. Let there be K states, s_{1},s_{2}...s_{K}. EXPLANATION:Let's solve for a single D first. Let's say D has prime factors p_{1}^{a1}, p_{2}^{a2} ... p_{K}^{aK}, where all p_{i} are unique.
So, we can clearly see that our dp[n,x] is dependent on dp[n1,y], where x and y are two different masks/states. We can use matrix exponentiation here because in one state in our dp, answer for n is dependent on answer for n1 and the transition among other states is not dependent on n. So, we form the transition matrix, where we set at transit[i][j], the number of ways to reach mask j from mask i . Sum of all elements in (2^{K}1)'th (all bits of D are set) row of N1'th power of this transition matrix, will give us the answer, in accordance with the technique explained above. Try to prove how this works. So, complexity for single D is O(log N * (2^{K*3})). Note matrix multiplication of sizes P*P takes O(P^{3}). And, maximum K is until 235711*13... is smaller than 1000(since D<1000). So, max K is 4. Total complexity for single D is O(log N * 2^{12}). Doing it for 1000 such values of D will take O(log N * 2^{22}) worst case. Note it will be really lower than that because of variation in K. SOLUTIONS:
This question is marked "community wiki".
asked 12 Jan '15, 15:08

This problem can be solved easily with inclusion exclusion principal too . http://www.codechef.com/viewsolution/5846988 Heres my solution . First factorize all the numbers in the form d = p * q * r * s where p,q,r and s are powers of prime numbers . Do this for all numbers from L to R . Then apply inclusion exclusion . See the code for more understanding answered 12 Jan '15, 16:00
exactly what i did..
(12 Jan '15, 16:55)
The constraints were low enough to use IEP for at max '4' elements.
(12 Jan '15, 19:45)

Inclusion Exclusion. Helped by a pen and lots of paper. Time Complexity is O(log(n)*2^15). That's almost 250 times faster than required. Made me wonder for a long time if I was missing something. answered 13 Jan '15, 00:43

Another Inclusion Exclusion guy here. Having used python, I did not have to hardcode for different number of factors. from itertools import combinations FTFW xD answered 13 Jan '15, 09:28

Hi I can't open neither setter's solution nor tester solution, can you please check this links. Thanks. answered 21 Jan '15, 00:05

can anyone explain the editorial for newbies like me so that we can progress further, im not getting anything in the editorial as i dont know anything about bit masks.
link
This answer is marked "community wiki".
answered 27 May '15, 17:39

The solution links of setter and tester are not working. Can you please check that? answered 21 Jan '15, 14:28
