SEALCM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM-HARD

PRE-REQUISITES:

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* ≤ M, A* - 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 (109 + 7).

TECHNIQUE:

I will suggest to specifically read the whole post given in pre-requisite if you are not aware about this technique.

Let there be K states, s1,s2…sK.
For each state si where i = 1 to K recurrence is defined as:
f(n,si) = sum {j=1 to K} c{i,j} f(n-1,sj).
We define a transition matrix M where M[j]=c{i,j}*.
Let’s consider M{N-1}. Sum of all elements in row i will give us f(N,si) assuming f(0,i)=0 forall i.

EXPLANATION:

Let’s solve for a single D first. Let’s say D has prime factors p1a1, p2a2 … pKaK, where all pi are unique.
We form a simple dp of dp[n,mask], which denotes the answer for N=n and D=product [pia_i], if i’th bit is set in mask. So, mask is a K bit number.
A simple recurrence would be:

&ret = dp[n,mask]
primes[] //prime factors of D.
count[] //count* denotes count of i'th prime in D
ret=0
for i = 0 to size(primes)-1:
    for j = 1 to M:
        //if j is kept at n'th index
        //and keeping it satisfies the i'th set bit condition
        //ie. count of primes* in j is greater than or equal to count*
        if count_prime(primes* in j) >= count*
            //set the i'th bit, add to current ret
            ret += dp[n-1, mask|(1<<i)]

So, we can clearly see that our dp[n,x] is dependent on dp[n-1,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 n-1 and the transition among other states is not dependent on n.

So, we form the transition matrix, where we set at transit[j]*, the number of ways to reach mask j from mask i . Sum of all elements in (2K-1)'th (all bits of D are set) row of N-1’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 * (2K*3)). Note matrix multiplication of sizes P*P takes O(P3).
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 * 212).

Doing it for 1000 such values of D will take O(log N * 222) worst case. Note it will be really lower than that because of variation in K.

SOLUTIONS:

Setter’s solution
Tester’s solution

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

16 Likes

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.

http://www.codechef.com/viewsolution/5867632

3 Likes

Another Inclusion Exclusion guy here. Having used python, I did not have to hard-code for different number of factors.

from itertools import combinations FTFW xD

http://www.codechef.com/viewsolution/5835895

3 Likes

Any idea someone how to use the fact, that N, M <= 10? Brute force worked fine for test cases, but I didn’t try for 10^10…

1 Like

Hi

I can’t open neither setter’s solution nor tester solution, can you please check this links.

Thanks.

1 Like

The solution links of setter and tester are not working. Can you please check that?

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.

1 Like

exactly what i did…

The constraints were low enough to use IEP for at max ‘4’ elements.

To explore N, M <= 10 we can use a simple dynamic programming algorithm.

First, note that the maximum LCM of an array with numbers 1…10 is 2520 (5 * 7 * 8 * 9). So our search state will be how many arrays are there with X numbers and lcm L. This yields 10*2520 states and we need to check all numbers 1…N and all lcms 1…2520.

My code: http://www.codechef.com/viewsolution/5751475

1 Like

Thanks :wink: