Sereja and Permutations 3
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.Let p be a permutation of integers 1, ..., N. Lets call p good if there is at least one pair of indices (i,j) such that i < j and p[i] > j, p[j] > i. Sereja is interested in the number of permutations p of 1, ..., N that are good. This might seem easy at first, but Sereja is only interested in permutations that obey a list of M additional rules. Rule number i (1 ≤ i ≤ M) in Sereja's list says p(Xi) should equal Vi. Help Sereja count number of good permutations that obey the M additional constraints. As this number can be quite large, you should only output its value modulo 2000000011.
InputThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case starts with line that contains two numbers N, M. The rest of the test cases consists of M lines describing Sereja's additional rules. The i'th such line gives the integers Xi and Vi.
OutputOutput one line per test case that gives the number of good permutations obeying Sereja's constraints modulo 2000000011.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10^9
- 0 ≤ M ≤ 10^4
- 1 ≤ Xi, Vi ≤ N
Input: 2 3 0 3 2 3 1 1 2 Output: 1 0
Example case 1. The only good permutation is 3,2,1 (i = 1, j = 2).
- Subtask #1: 1 ≤ N ≤ 8 (5 points)
- Subtask #2: 1 ≤ N ≤ 20 (10 points)
- Subtask #3: 1 ≤ N ≤ 1000 (15 points)
- Subtask #4: 1 ≤ N ≤ 10000 (15 points)
- Subtask #5: 1 ≤ N ≤ 100000000 (20 points)
- Subtask #6: original (35 points)
|Tags||dynamic-programming, hard, matrix-expo, nov16, sereja|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.