PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Aryan
Tester: Aryan
Editorialist: Surya Prakash
DIFFICULTY:
3127
PREREQUISITES:
Longest Increasing Subsequence, Linear Recurrences, Berlekamp-Massey Algorithm
PROBLEM:
For any array, A, define f(A) to be equal to the length of the longest strictly increasing subsequence of A. Given N, M and P, compute the sum of f(A)^P over all arrays A of length N taking values in \{1, 2 \dots M\} modulo 754974721.
EXPLANATION:
Given an array A of length N, we can compute the length of the longest strictly increasing subsequence in \mathcal{O}(N \log(N)). See here for reference. Consider the vector that we maintain in this algorithm. Since we are considering strictly increasing subsequence, the values in this vector will always be distinct. Also, the length of LIS is equal to the length of this vector at the end of the algorithm. So we can use the following algorithm to compute LIS (which is just a slight modification in the implementation) from here.
set<int> S;
for(int i = 0; i < N; i++){
auto it = S.lower_bound(A[i]);
if(it != S.end())S.erase(it);
S.insert(A[i]);
}
cout << S.size() << '\n';
Notice that at each iteration, all that matters is the elements that are present in the set S. And since we have the constraint M \leq 14, we can use a bitmask to represent the set S.
Now create a graph with nodes being all possible sets S i.e. all 2^M subsets of \{1, 2 \dots M\}. For any bitmask u and for any 1 \leq j \leq M, we can find the bitmask v that we get if the current set is u and the next element in the sequence j. Add an edge from u to v with label j. We get a directed graph with 2^M vertices and M\times 2^M directed edges.
Clearly, there is a bijection between the set of all sequences of length N taking values in \{1,2 \dots M\} and the set of all paths of length N starting from node 0 in our graph. Also, for any array, A, the final node in the corresponding path is equal to the set that we get by running the above algorithm on A and f(A) is equal to the number of bits set in the final node of the corresponding path. So the problem boils down to computing the number of paths of length N from node 0 to node u and then multiplying this with (\text{number of bits set in }u)^P and then summing this up over the sets (bitmasks) u i.e.
Let A be the adjacency matrix of the graph we constructed. Clearly, the number of paths of length N from node i to node j is equal to the (i, j)-th entry in the matrix A^N. So, the number of paths from node 0 to node i is equal to i-th entry in the column vector A^N e_0 where e_0 is the column vector with 1 at 0-th index and 0 everywhere else. Now define the column vector c of length 2^M with c_u being equal to (\text{number of bits set in }u)^P. Then, the required answer is equal to c^T A^N e_0, where c^T is the transpose of the vector c.
Since A is a square matrix of size 2^M, it will exceed the time limit if we use matrix exponentiation to compute c^T A^N e_0.
Let p_n = c^T A^N e_0. From the Cayley-Hamiltonian theorem, the matrix A satisfies its characteristic polynomial i.e. if p is the characteristic polynomial of A, then p(A) = 0. And we have that the degree of polynomial p is equal to 2^M. Suppose
where L = 2^M. Since p(A) = 0, it implies that
So, for any N \geq L, we have
This implies that for any N \geq L, we have
i.e. a_L d_N + \ldots + a_1 d_{N - L + 1} + a_0 d_{N - L} = 0. So, the sequence \{d_N\} satisfies a linear recurrence relation. It’s very difficult to come up with an explicit theoretical upper bound on the degree of linear recurrence corresponding to this sequence, but it can be very easily verified using the Berlekamp-Massey algorithm that for any fixed M and P, the degree of the linear recurrence is less than 500 due to the special structure of this graph.
So we compute the values of d_N for the first 2 \cdot 500 = 1000 values of N and then use the Berlekamp-Massey algorithm to come up with coefficients of the linear recurrence relation. Then, answering a query takes \mathcal{O}(d) run time where d is the degree of the linear recurrence which is less than 500. The value of d_N for the first 1000 values can be computed using dynamic programming. Define dp[u][k] to be the number of paths from 0 to u of length k. Then
And since there are exactly M \times 2^M edges, this transition step has a time complexity of \mathcal{O}(M \times 2^M).
Let A = 500. So, given M and P, we precompute d_n for n \leq 2A in \mathcal{O}(A \cdot M \cdot 2^M). And then use the Berlekamp-Mersey algorithm to compute the coefficients of linear recurrence in \mathcal{O}(A^2). Now for a given N, we can compute d_N using the algorithm described here in \mathcal{O}(A^2 \log(N)) or \mathcal{O}(A \log(A) \log(N)).
TIME COMPLEXITY:
\mathcal{O}(A\cdot M \cdot 2^M + A^2 + Q \cdot A \log(A) \log(N))