[Solution] Top-Notch Insertions solution codeforces

Top-Notch Insertions solution codeforces

Consider the insertion sort algorithm used to sort an integer sequence [a1,a2,,an][a1,a2,…,an] of length nn in non-decreasing order.

For each ii in order from 22 to nn, do the following. If aiai1ai≥ai−1, do nothing and move on to the next value of ii. Otherwise, find the smallest jj such that ai<ajai<aj, shift the elements on positions from jj to i1i−1 by one position to the right, and write down the initial value of aiai to position jj. In this case we’ll say that we performed an insertion of an element from position ii to position jj.

It can be noticed that after processing any ii, the prefix of the sequence [a1,a2,,ai][a1,a2,…,ai] is sorted in non-decreasing order, therefore, the algorithm indeed sorts any sequence.

For example, sorting [4,5,3,1,3][4,5,3,1,3] proceeds as follows:

  • i=2i=2a2a1a2≥a1, do nothing;
  • i=3i=3j=1j=1, insert from position 33 to position 11[3,4,5,1,3][3,4,5,1,3];
  • i=4i=4j=1j=1, insert from position 44 to position 11[1,3,4,5,3][1,3,4,5,3];
  • i=5i=5j=3j=3, insert from position 55 to position 33[1,3,3,4,5][1,3,3,4,5].

You are given an integer nn and a list of mm integer pairs (xi,yi)(xi,yi). We are interested in sequences such that if you sort them using the above algorithm, exactly mm insertions will be performed: first from position x1x1 to position y1y1, then from position x2x2 to position y2y2, …, finally, from position xmxm to position ymym.

How many sequences of length nn consisting of (not necessarily distinct) integers between 11 and nn, inclusive, satisfy the above condition? Print this number modulo 998244353998244353.


Each test contains multiple test cases. The first line contains the number of test cases tt (1t1051≤t≤105). Description of the test cases follows.

The first line of each test case contains two integers nn and mm (2n21052≤n≤2⋅1050m<n0≤m<n) — the length of the sequence and the number of insertions.

The ii-th of the following mm lines contains two integers xixi and yiyi (2x1<x2<<xmn2≤x1<x2<…<xm≤n1yi<xi1≤yi<xi). These lines describe the sequence of insertions in chronological order.

It is guaranteed that the sum of mm over all test cases does not exceed 21052⋅105Note that there is no constraint on the sum of nn of the same kind.

Output Top-Notch Insertions solution codeforces

For each test case, print the number of sequences of length nn consisting of integers from 11 to nn such that sorting them with the described algorithm produces the given sequence of insertions, modulo 998244353998244353.

Example Top-Notch Insertions solution codeforces
input Top-Notch Insertions solution codeforces

Copy Top-Notch Insertions solution codeforces
3 0
3 2
2 1
3 1
5 3
3 1
4 1
5 3


In the first test case, the algorithm performs no insertions — therefore, the initial sequence is already sorted in non-decreasing order. There are 1010 such sequences: [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3][1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3].

In the second test case, the only sequence satisfying the conditions is [3,2,1][3,2,1].

In the third test case, [4,5,3,1,3][4,5,3,1,3] is one of the sought sequences.



Solution: Click here

Top-Notch Insertions solution codeforcessolution codeforcescodeforces solutioncodeforces freshersonline

Leave a Comment