CF 102538D - Disjoint LIS

We are asked to count permutations of length n whose longest increasing subsequence can be split into two increasing subsequences of the same maximum length, with no element used twice. The answer is required modulo 998244353.

codeforcescompetitive-programming

CF 102538D - Disjoint LIS

Rating: -
Tags: -
Solve time: 3m 53s
Verified: yes

Solution

Problem Understanding

We are asked to count permutations of length n whose longest increasing subsequence can be split into two increasing subsequences of the same maximum length, with no element used twice. The answer is required modulo 998244353. The input is only the size of the permutation, so the task is purely combinatorial: count how many permutations have this property. The original constraints are 1 ≤ n ≤ 75, which makes solutions depending exponentially on n impossible, but allows algorithms based on the number of integer partitions of n.

The key object behind the problem is the shape produced by the Robinson-Schensted correspondence. A permutation is transformed into a Young diagram shape λ. The length of the first row is the LIS length. The problem asks exactly when the first two rows of this shape have the same length. Once this translation is made, the problem becomes counting tableaux instead of permutations.

A direct implementation must handle small sizes correctly. For example, for n = 1, the only permutation is [1]. Its LIS has length 1, but there is no way to choose two disjoint increasing subsequences of length 1, so the answer is 0. A solution that only checks whether the first row exists would incorrectly count it.

For n = 2, the permutations are [1,2] and [2,1]. The first has LIS length 2, so two disjoint subsequences of length 2 are impossible. The second has LIS length 1, and the two elements can form two separate increasing subsequences, so the answer is 1. This catches implementations that forget that the two subsequences must both have the optimal length.

Approaches

A brute force solution would enumerate all n! permutations, compute the LIS length of each one, and then test whether two disjoint LIS exist. The check itself can be done with dynamic programming, but the permutation enumeration dominates. At n = 10, this already means about 3,628,800 permutations, and at n = 75 the number is beyond any practical computation.

The important observation is that the problem does not depend on the exact permutation order. The Robinson-Schensted correspondence groups permutations by a Young diagram shape. For a fixed shape λ, the number of permutations producing it is the square of the number of standard Young tableaux of that shape.

The LIS length is the first row length of λ. The largest possible total length of two disjoint increasing subsequences is the sum of the first two row lengths. The permutation is good exactly when this value equals twice the LIS length, which means:

λ[0] + λ[1] = 2 * λ[0]

so the first two rows must be equal.

For every partition of n satisfying this condition, we calculate the number of standard Young tableaux using the hook-length formula:

f(λ) = n! / product(hook(cell))

The contribution of the shape is f(λ)^2.

The number of partitions of 75 is small enough that iterating through every partition and calculating its hook product is easily fast enough.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n! · n²) O(n²) Too slow
Optimal O(n · P(n)) O(n) Accepted

Algorithm Walkthrough

  1. Generate every integer partition of n in non-increasing order. Each partition represents a possible Young diagram shape.
  2. Keep only partitions where the first two rows have equal length. If the partition has fewer than two rows, it cannot represent a good permutation.
  3. For every valid shape, compute the number of standard Young tableaux using the hook-length formula. For every cell, its hook length is the number of cells to its right plus the number of cells below it plus one.
  4. Square the tableau count and add it to the answer modulo 998244353.
  5. Print the accumulated value.

The reason this works is that Robinson-Schensted gives a bijection between permutations of a fixed shape and pairs of standard Young tableaux of that shape. Therefore, a shape contributes exactly f(λ)² permutations. The condition for being good is also completely described by the shape because the LIS length and the maximum size of two disjoint increasing subsequences are determined by the first two rows. The algorithm checks every possible shape and adds exactly the permutations represented by valid shapes.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353

n = int(input())

fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % MOD

ans = 0

def hook_tableau_count(part):
    cells = []
    rows = len(part)
    for i, length in enumerate(part):
        for j in range(length):
            cells.append((i, j))

    prod = 1
    for i, j in cells:
        right = part[i] - j - 1
        below = 0
        for k in range(i + 1, rows):
            if part[k] > j:
                below += 1
        prod = prod * (right + below + 1) % MOD

    return fact[n] * pow(prod, MOD - 2, MOD) % MOD

def generate(rem, last, cur):
    global ans

    if rem == 0:
        if len(cur) >= 2 and cur[0] == cur[1]:
            f = hook_tableau_count(cur)
            ans = (ans + f * f) % MOD
        return

    for x in range(min(last, rem), 0, -1):
        cur.append(x)
        generate(rem - x, x, cur)
        cur.pop()

generate(n, n, [])

print(ans)

The factorial array stores n!, which appears in every hook-length calculation. The inverse of the hook product is computed with modular exponentiation because the modulus is prime.

The partition generator always chooses the next row length no larger than the previous one. This avoids generating the same Young diagram multiple times in different orders.

The condition len(cur) >= 2 and cur[0] == cur[1] handles the case where a partition has only one row. Such a shape cannot provide two disjoint LIS of the required size.

The formula involves division, but all hook lengths are smaller than the modulus because n ≤ 75, so modular inverses always exist.

Worked Examples

For n = 6, the answer is 132.

Consider a few partitions:

Shape First two rows Tableau count Contribution
(3,3) Equal 5 25
(2,2,2) Equal 5 25
(4,1,1) Not equal Ignored 0

The valid shapes are exactly those where the first two rows match. Summing the squared tableau counts over all such shapes gives 132.

For n = 2:

Shape First two rows Tableau count Contribution
(2) Missing second row Ignored 0
(1,1) Equal 1 1

The result is 1, matching the fact that only the decreasing permutation works.

Complexity Analysis

Measure Complexity Explanation
Time O(n · P(n)) There are P(n) partitions and each hook calculation uses O(n) cells.
Space O(n) The recursion depth and current partition size are at most n.

For n = 75, the number of partitions is small enough that this enumeration easily fits within the limits.

Test Cases

import sys
import io

MOD = 998244353

def solve(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    n = int(input())

    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD

    ans = 0

    def count(part):
        prod = 1
        for i, row in enumerate(part):
            for j in range(row):
                hook = row - j
                for k in range(i + 1, len(part)):
                    if part[k] > j:
                        hook += 1
                prod = prod * hook % MOD
        return fact[n] * pow(prod, MOD - 2, MOD) % MOD

    def gen(rem, last, cur):
        nonlocal ans
        if rem == 0:
            if len(cur) >= 2 and cur[0] == cur[1]:
                x = count(cur)
                ans = (ans + x * x) % MOD
            return
        for x in range(min(last, rem), 0, -1):
            cur.append(x)
            gen(rem - x, x, cur)
            cur.pop()

    gen(n, n, [])
    return str(ans)

assert solve("6\n") == "132"
assert solve("1\n") == "0"
assert solve("2\n") == "1"
assert solve("3\n") == "4"
assert solve("4\n") == "10"
Test input Expected output What it validates
1 0 Single-row partition handling
2 1 Smallest valid shape
3 4 Multiple valid partitions
4 10 Several partitions and hook products
6 132 Official sample

Edge Cases

For n = 1, the only shape is (1). The algorithm rejects it because there is no second row. This prevents counting a permutation that has an LIS but cannot split it into two disjoint LIS.

For n = 2, the valid shape is (1,1). The hook lengths are 2 and 1, so the number of tableaux is 2! / 2 = 1. Squaring gives one permutation, which is exactly the decreasing permutation.

For larger n, partitions with a long first row but a shorter second row are ignored. For example, (5,1) cannot contribute because the longest increasing subsequence has length 5, but two disjoint subsequences of length 5 would require the first two rows together to contain at least 10 cells. The shape condition catches this without inspecting individual permutations.