Method Resolution Order
All submissions for this problem are available.
Zotlin is an object-oriented programming language that provides features such as Classes and Functions. Zotlin also has the following features:
- A function with the same name and same declarations can have different implementations in different classes.
- Each class can inherit zero or more classes (excluding itself). If Class A inherits Class B, we say that Class A is a child of Class B.
- A class cannot inherit another class if a cycle is formed by inheritance.
For example, if Class A inherits Class B and Class B inherits Class C, then Class C cannot inherit Class A.
A Class X is called an ancestor of Class Y, if Y inherits directly or indirectly from Class X. ie, say Class Y inherits from Class Z, which inherits from Class X. Then Class X is an ancestor of both Class Y and Class Z.
Mr. Zourist — a very popular programmer — wrote a program in Zotlin with N classes numbered from 1 to N. Some of these classes have an implementation of a function F. The Zotlin compiler needs to determine which definition of function F should be called for an object of Class 1.
In order to deterministically decide which implementation of function F to use, the compiler uses a list called the Resolution Order (RO list). This is a list containing Class 1 and its ancestors. The compiler iterates through this list to search for a class that contains an implementation of function F.
The properties of an RO list are as follows:
- The 1st member of the list is Class 1.
- The list contains only the ancestors of Class 1. All the Classes in the list are unique.
- It is guaranteed that no Class occurs after any of its ancestors in the list.
Let's define the Special RO list as an RO list of length N where the ith member in the list is Class i. That is, the Special RO list is [1, 2, 3, ... , N].
Find out the number of distinct class-inheritance hierarchies Mr. Zourist could have created in his program for which one of the valid RO lists is the Special RO list. Print your output modulo 109 + 7.
Two class-inheritance hierarchies are considered different if they have at least one class that inherits a different list of classes.
The first line of input contains a positive integer T - denoting the total number of testcases.
T lines follow - the ith line contains a single positive integer N- denoting the number of classes written by Mr. Zourist.
For each testcase, print the required number of distinct class-inheritance hierarchies modulo 109 + 7 on a new line.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 105
2 3 6 Output 3 9765
Explanation for testcase 1:
Let "class X" denote that X does not inherit any class
Let "class X(Y)" denote that X inherits Y
Let "class X(Y, Z)" denote that X inherits Y, Z
class 2 class 3 class 1(2, 3)
class 3 class 1(2) class 2(3)
class 3 class 1(2, 3) class 2(3)
These are the three valid class-inheritance hierarchies, and hence the answer is 3.
Note that the following hierarchy is not valid:
class 1(2) class 2 class 3This is because 3 should have been an ancestor of 1, but in the above hierarchy, 3 is a stand-alone class.
|Tags||acm17chn, chn17rol, dynamic-programming, easy, wittyceaser|
|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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.