PEREXP - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Factorization, elementary combinatorics

PROBLEM:

A permutation P can be transformed to an array A by performing the following operation:

  • Choose a positive integer X.
  • Then, for each i = 1, 2, \ldots, N, set either A_i = P_i or A_i = P_i\cdot X

You’re given the final array A.
Count the number of P that can form A using the given operation.

EXPLANATION:

Since the elements of P are initially distinct, this means their products with X are also distinct.
In particular, this means that the created array A can contain any given integer at most twice: once from the original P, and once via some element of P multiplied by X.

Thus, if some element appears in A three or more times, no P can create it; and the answer is immediately 0.

So, every integer from 1 to N appears either 0, 1, or 2 times.

First, consider the case where every element appears exactly once.
Note that this means we have a copy of every element from 1 to N, i.e. A is itself a permutation.

In this case, the only valid initial permutation is P = A itself.
The answer in this case is hence 1.

Next, consider the case where there are repeated elements.

Let Y be some element that appears twice.
Recall that for this to be the case, one copy of Y must be the initial one present in P, while the other copy must come from some element being multiplied by X.

In particular, X must be a divisor of Y.

Let’s now fix the value of X to be some divisor of Y, and try to count the number of valid permutations.
Note that different values of X will lead to different permutations (because the values of \frac{Y}{X} will be different), so we can simply add up the answers to all X and there will be no overcounting.

Once X is fixed, let’s try to understand how we can generate the base permutation P from A.
Note that this corresponds to dividing some elements of A by X.

One way is to process values in ascending order.
That is, let’s iterate through values from 1 to N; and say we’re currently looking at the value v.
We’ll also maintain the condition that we already have exactly one copy of each of the values 1, 2, 3, \ldots, v-1 (maybe after performing some divisions.)
Then,

  • If we have one copy of v already, we’re happy.
  • If we have two copies of v, no solution can exist - to get rid of the extra copy of v we’ll have to divide it; but then it becomes strictly smaller and we already have one copy of everything \lt v, so something smaller will be duplicated instead.
    So, if we reach such a state, this choice of X is invalid, and there are 0 reachable permutations.
  • If we have zero copies of v, then we need to obtain one copy via division.
    So, we must look at v\cdot X. Now,
    • If there are no copies of v\cdot X, we’re in trouble - it’s impossible to obtain v.
      So, this X is invalid, and there are 0 reachable permutations.
    • If there’s exactly one copy of v\cdot X, it must be divided to obtain v.
      After this, we’ll instead have zero copies of v\cdot X.
    • If there are two copies of v\cdot X, one of them must be divided to obtain v.
      It doesn’t matter which one is divided; so we multiply the count by 2.

Once we’ve processed all N values this way, we’ll also know the number of possible base permutations.
It can in fact be verified that this count will be either 0 or 2^k, where k equals the number of repeated elements in A (though this doesn’t particularly matter for the purposes of just solving the problem.)

For a fixed X, this process takes \mathcal{O}(N) time.
The number of values of X we check is bounded by the number of divisors of the chosen repeated value Y.
This is trivially bounded by \mathcal{O}(\sqrt N) since Y \le N. A slightly more precise bound is to note that any number \le 10^5 has no more than 128 divisors, so we’re bounded by 128\cdot N.

TIME COMPLEXITY:

\mathcal{O}(N\cdot d(N)) per testcase, where d(N) denotes maximum number of divisors of some integer \le N (giving d(N)\le 128).

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    freq = [0]*(n+1)
    repeat = 0
    for x in a:
        freq[x] += 1
        if freq[x] > 1: repeat = x
    
    if repeat == 0: # permutation
        print(1)
        continue

    ans = 0
    for x in range(1, n+1):
        if repeat%x != 0: continue

        cur = freq[:]
        ct = 1
        for i in range(1, n+1):
            if cur[i] == 1: continue 
            elif cur[i] > 1: ct = 0
            else:
                if i*x > n or cur[i*x] == 0: ct = 0
                else:
                    if cur[i*x] == 2: ct = (ct * 2) % mod
                    cur[i*x] -= 1
        ans = (ans + ct) % mod
    print(ans)