Chef and Polyhedron
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a convex polyhedron. Each face of polyhedron is a regular polygon. All polyhedral angles are equal. You have to find number of different ways to paint all the faces of the polyhedron in one of the C colors. Note that two painting of the polyhedron are said to be same, if one can be reached from other by a sequence of rotations or mirror reflections of the polyhedron. As this value could be large, output it by modulo 109+7.
There is a single test case.
First line of the input contains two positive integers - N (number faces of the polyhedron) and C (number of possible colors)
Next N lines contain information about the faces of polyhedron:
First number of each line contains an integer ki denoting number of faces adjacent to i-th face. Next ki integers in the same line denote the faces adjacent to i-th face.
Output a single integer in a line denoting number of ways to color polyhedron in different ways modulo 109+7
- 4 ≤ N ≤ 25
- 1 ≤ C ≤ 109
- Subtask 1: Polyhedron is regular. Points - 20
- Subtask 2: Original constraints. Points - 80
Input: 6 2 4 2 3 4 5 4 1 3 5 6 4 1 2 4 6 4 1 3 5 6 4 1 2 4 6 4 2 3 4 5 Output: 10
Input: 4 4 3 2 3 4 3 1 3 4 3 1 2 4 3 1 2 3 Output: 35
|Tags||burnside, hard, july16, mgch|
|Time Limit:||1 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.