Chef And A Complete Graph
All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Chef loves to play with graphs. Today, Chef has a complete graph G consisting of N vertices and he is eager to count the number of non-empty subsets of the edge set of G such that the removal of any chosen subset separates the graph into exactly K connected components. Chef is unable to solve this task on his own and has, therefore, requested your assistance. Please help him.
Since the required answer can be very large, Print it modulo M.
First line of input contains a single integer T denoting the number of test cases. First and the only line of each test case contains 3 space separated integers — N, K and M — denoting the number of vertices in the graph G, required number of connected components, and the modulus.
For each test case, output the required answer.
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 100
- 1 ≤ K ≤ N
- 1 ≤ M ≤ 109
- Subtask 1: 1 ≤ N ≤ 6 ( 25 pts )
- Subtask 2: 1 ≤ N ≤ 50 ( 25 pts )
- Subtask 3: 1 ≤ N ≤ 100, M is prime ( 25 pts )
- Subtask 4: Original Constraints ( 25 pts )
Input: 5 2 2 3 3 1 5 4 3 7 4 2 11 5 1 10 Output: 1 3 6 8 7
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.