Nanami_chan's blog

How to solve spoj COPSEQ?
By Nanami_chan, history, 6 years ago, In English

Problem link: Here

Harder version of problem: Here

Abridged problem statement (for non-hard version):
Given n <= 10^5 and m <= 10^18, how many sequence of length n satisfies the following conditions:
1. Every number in the sequence is positive divisor of m
2. Two adjacent element is not coprime.
Numbers can be repeated, different ordering counts as different sequence.

The best way I could think of right now is factorizing using pollard rho and then do O(N*D*D) naive dp where D is number of divisors. Problem is D can be up to almost 10^5 for some highly composite numbers.

Another idea that comes to mind is to treat divisors as vertex, connect them if they can be adjacent in the resulting sequence, and find total number of walks with length (n-1) which can be done using matrix power. But this seems even slower because matrix can be large.

Any help is appreciated, thanks!

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nanami_chan (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not sure if this helps, but the maximum number of coprime divisor pairs of a number<=1e18 is about 3.3e7. If we can form some kind of divide conquer approach, and subtract answers for the coprime pairs from all pairs when merging two sequences, then maybe this can be squeezed in the time limit.

Also, I believe the dp will take O(D*D*N) time if done naively, can you share the O(D*N) approach?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh yeah I mean O(N*D*D). Thanks for your input! I'll try to think about it

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you replace D with 2^{number of primes} and D*D with O(3^{number of primes}), but this solution not pass :(. Great problem...

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nanami_chan (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Let Ci, where i > 0, be the number of primes in the factorization of m with power i. Say k is the highest such that Ck > 0. Now, your state is a k-vector (v1, ..., vk), such that 0 <= vi <= Ci for all i. For transitions we don't care at all what the powers of primes in the previous integer were, and we are symmetric to all primes with the same power in the original integer, so we can do this. Let the maximum number of these k-vectors for any m <= 10^18 be S. S is probably pretty small, I'll calculate the exact amount later.

Then you can just make a matrix with these states, and easy-to-calculate transitions, and calculate the answer in O(S^3 log (N)).

Not sure if this works, depends on what S is.

EDIT: looks like S is 64, so this definitely works. Here's the code I used to calculate this

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Sorry but I don't quite understand how the matrix will look like. If it's not too much trouble could you provide an example?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      Say that M = 22·32·5 = 180.

      Now C1 = 1, C2 = 2, and our six possible states are:

      1. (0, 0) = 1
      4. (1, 0) = 5

      Call the transition matrix T. For two states a and b, with prime counts (a1, a2, ..., ak) and (b1, b2, ..., bk) (where ai, bi ≤ Ci). Denote by size(a) the number of divisors of M in the state a.

      The transition Ta, b can be calculated as follows: fix a and b, and define ri as the number of ways to pick the primes from the first i groups in b s.t. so far no prime appears in both a and b. Then r0 = 1 and

      \begin{equation*} r_{i} = r_{i-1} \binom{C_{i} — a_i}{b_i} \cdot i^{b_i} \end{equation*}

      and the transition Ta, b is Ta, b = size(b) - rk. For example, in the example case above the transition from state 5 to state 2 has r2 = 2 and size(2) = 4 so T5, 2 = 2.

      → Reply