Shuffled Stones
Time limit3sMemory limit1024 MB
Given N and a pair X, Y, count the sequences of 2N stones with longest decreasing subsequence 2 in which X and Y are a pair, modulo 998244353.
- Level
Hard8 of 10
- Topics
- Combinatorics, Math
- Solved
- No attempts yet
Problem
While walking down the street, Chanwoo found stones on the ground, with the integers from to written on them in order. Bothered by the neat order, he decided to shuffle the stones. He grouped the stones into pairs of two, then swapped the positions of the two stones in each pair. This produced a new sequence .
Pleased with the mess he had made, Chanwoo noticed an interesting property. The longest decreasing subsequence of the shuffled sequence has length only . He wanted to take a photo of it, but his phone battery was dead. Instead, he took one pair of stones that he had paired.
Back home, Chanwoo wanted to reconstruct the sequence, but he remembers only three things: and were paired, the total number of stones is , and the longest decreasing subsequence of the sequence has length . Given and the pair , , count how many sequences satisfy these conditions.
Input
The first line contains , , and separated by spaces. (; ; )
Output
Print the number of valid sequences modulo .
Hint
You can form a subsequence by removing some numbers from a sequence. Among the subsequences formed this way, the longest one sorted in decreasing order is called the longest decreasing subsequence.