PROBLEM LINK :
Setter : Rushil Patel
Tester : Vishal Mahavar
DIFFICULTY :
Medium-Hard
PREREQUISITES :
Dynamic Programming, Berlekamp Massey, Polynomials
PROBLEM
Given a matrix with X rows and N columns. You select segments for each column (1 \leq L _{i} \leq R_{i} \leq X for 1 \leq i \leq N) such that intersection between any two adjacent segments (i.e. (L_{i},R_{i}) and (L_{i+1}, R_{i+1}) for 1 \leq i \leq N-1) is not empty. You have to find number of ways in which such segments can be selected.
EXPLANATION
We can use dynamic programming to solve this problem in O(N * X^2) using prefix and suffix sums of previous dp states answers. Note that this can be reduced to O(N * X) after some observation. The reduced version also uses prefix and suffix sums. Here we notice that for any given state the transitions are not dependent on variable that represents the column, hence the dp values will have a recurrence relation of O(X) size. In our case, we found that for given X, the sequence of dp values (for N = 1, 2, 3, ...) has a recurrence relation of size exactly X.
We use berlekamp massey to find this recurrence relation of size X. Now the only thing remaining is to find the N^{th} value in the sequence. We can notice that because X can be pretty large, we can’t use matrix exponentiation to find N^{th} term. Hence we use a more advance technique than matrix exponentiation to get N^{th} term. It uses polynomials and some clever tricks using characteristic polynomial (You can find the details in this blog).
Then we can use the formula for probability.
Probability = \dfrac{N^{th} \text{ term in sequence}}{(1 + \dfrac{X * (X + 1)}{2})^N} \text{ modulo 998244353}
PROOF
We want a proof that dp value sequence follows a recurrence relation of size X. Here our state is (i , j) and it’s value can be represented as,
dp[i][j] = \sum_{k=1}^{X} dp[i - 1][k] * v[k][j]
If we take dp[i] as a column vector (i.e. X * 1), then dp[i] = T^{i} * dp[0] where T is the transition matrix of size X * X. According to Cayley Hamilton Theorem, power series of a matrix of size X * X follows a recurrence relation of size X.
Hence, T^{i} = \sum_{k=1}^{X} c_{k} * T^{i - k}, i \geq X
dp[i] = (\sum_{k=1}^{X} c_{k} * T^{i - k}) * dp[0]
dp[i] = \sum_{k=1}^{X} (c_{k} * T^{i - k} * dp[0])
dp[i] = \sum_{k=1}^{X} (c_{k} * dp[i - k])
Hence dp[i] follows a recurrence of size exactly X.
TIME COMPLEXITY
Time complexity of solution is O(X^2 + X*logX*logN) if you use NTT or O(X^2*logN) if you use naive polynomial multiplication. Both are good enough to pass.