PROBLEM LINK:
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[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 (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[i][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[i] 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[i] in j is greater than or equal to count[i]
if count_prime(primes[i] in j) >= count[i]
//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[i][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.
