1219. How Many Orders the Tasks Can Be Done In

There are n tasks numbered 1 to n and m rules, each saying that one task must be done before another. The rules never form a cycle. Report how many orders the tasks can be done in.

4 tasks, rules 1 before 2 and 3 before 4 -> 6 15 tasks, no rules -> 1307674368000 15 tasks in one chain -> 1

## What most people try first

Generate the n! orders and keep the ones obeying every rule. At n = 15 that is 1307674368000 orders, which is also the answer when there are no rules, so the method is hopeless for the same reason the answer is large. Even with rules that cut the answer down, the enumeration still walks the whole n! tree because it only discovers a violation at the end.

The first improvement is to build the order forwards, choosing at each step a task whose prerequisites are all done. That prunes a great deal and it is still O(n!) in the worst case, since with no rules nothing is ever pruned.

## The canonical state

Ask what a node of that forward search needs in order to know how many ways there are to finish. At a node, some set of tasks is done. Which tasks are available next depends on WHICH tasks are done, and not at all on the order they were done in. So the number of completions is a function of the done SET alone.

f(S) = 1 when S is every task f(S) = sum over tasks t not in S whose prerequisites are all in S of f(S + t)

There are 2^n sets, each computed once, each costing O(n). So O(2^n * n) instead of O(n!). At n = 15 that is 32768 states against 1.3 trillion orders, a ratio of forty million.

## Representing the set

A subset of up to 15 tasks is 15 bits of one integer, which is the only practical choice: it has to index the memo table. Store the prerequisites of each task as a bitmask too, and then "all prerequisites done" is the single test need[t] & ~done == 0.

In JavaScript the bitwise operators truncate to 32 bits, which is fine at 15 bits, and ~done is a 32-bit complement, so the test behaves as intended.

## Overflow

This is the part to get right. With no rules at all the answer is n!, and 15! = 1307674368000, which is about 1.3 * 10^12 and six hundred times INT_MAX = 2147483647. So the counter and every memo entry must be 64 bits: long long in C and C++, long in Java. In JavaScript a plain number is an exact integer below 2^53, about 9 * 10^15, so 1.3 * 10^12 is exact there and BigInt is not needed, provided no bitwise operator touches the count. That last point is a real hazard in this problem, because the masks next to the counts are manipulated with bitwise operators; the masks are 15-bit and the counts are not, and the two must not be mixed.

The limit is 15 because 16! = 20922789888000 would still fit in 64 bits but the memo table doubles with each task, and 15 keeps the whole table inside a comfortable allocation.

## The closed forms that check the answer

With no rules the answer is n!. With a single chain, meaning 1 before 2 and 2 before 3 and so on up to n, the answer is 1. And with m rules on DISJOINT pairs of tasks, the answer is n! / 2^m: each pair constrains its own two tasks independently, and of the two relative orders exactly one is allowed, so each rule halves the count. The tests include six disjoint pairs at n = 12, giving 12! / 64 = 7484400, and seven at n = 14, giving 14! / 128 = 681080400.

## Cost

O(2^n * n) time and O(2^n) memory, against O(n! * n) for the enumeration.

Constraints - `1 ≤ n ≤ 15` - `0 ≤ m ≤ 40` - `1 ≤ u, v ≤ n` and `u != v` - the rules never form a cycle - the answer can reach `15! = 1307674368000`, which does not fit in a signed 32-bit integer