### PROBLEM LINK:

**Author:** Vaibhav Tulsyan

**Tester:** Misha Chorniy

**Editorialist:** Animesh Fatehpuria

### PROBLEM

Compute number of DAGs with N nodes that satisfy the following properties:

- There is exactly 1 source node numbered 1. Let’s call this constraint A.
- Nodes 2, 3, \cdots, N are reachable from 1. Let’s call this constraint B.
- [1, 2, 3, \cdots, N] is a valid topological order of the DAG. Let’s call this constraint C.

Two ways are different if at least one node has a different set of ancestors.

Constraint: 1 \le N \le 10^5.

### EXPLANATION

One of the most important parts to solving this problem is parsing the problem statement carefully

and reducing it to the problem mentioned above. Reduction to the graph-theoretic version makes the problem

much more tractable.

I’ll provide some intuition about how to go about this problem before describing the formal

approach. It’s always a good idea to doodle on paper for problems like these to gain more insight.

It’s clear that for N = 1, the answer is 1. For N = 2, the answer will also be 1 in order

to satisfy constraint B. For N = 3, the answer is 3, as we can have the following DAGs defined by

these set of edges:

- E = \{1 \rightarrow 2, 2 \rightarrow 3\}
- E = \{1 \rightarrow 2, 1 \rightarrow 3\}
- E = \{1 \rightarrow 2, 1 \rightarrow 3, 2 \rightarrow 3\}

Now let’s search for some recursive structure. Since we want to satisfy constraint C, we can consider adding

the nodes one by one from 1, 2, \cdots, N, ensuring at each step that we satisfy constraint B. Note that

adding in this natural order is key here as it implicitly handles constraint C.

Define f(n) to be the number of *valid* DAGs with n nodes. How can we relate f(n) to f(n - 1)?

To answer this, first lets recap what we know about the DAGs considered by f(n - 1):

- It’s a
*valid*DAG with N - 1 nodes. - All nodes are reachable from 1. (Constraint B is satisfied)
- [1, 2, 3, \cdots, N - 1] is a valid topological order. (Constraint C is satisfied)

How can we extend these DAGs to valid DAGs with N nodes? It turns out that this is quite simple to do. We just need to add an edge from at least one node from the set \{1, 2, 3, \cdots, N - 1\} to N in order to satisfy both properties B and C. The number of ways to do this is equal to the number of *nonempty* subsets of \{1, 2, 3, \cdots, N - 1\} which is given by 2^{N - 1} - 1. Therefore, the recurrence we’re looking for is f(n) = f(n - 1) \cdot (2^{N - 1} - 1).

That’s it! We now have the simplest of recurrences for f(n), and we can precompute them using DP in O(n) time, and then answer each test case in O(1). The code will look as follows:

```
pw2[0] = 1; // Precompute Powers of 2
for (int i = 1; i < MAXN; ++i) {
pw2[i] = pw2[i - 1] * 2 % MOD;
}
f[1] = 1; // Precompute f(n) using the recurrence derived above
for (int i = 2; i < MAXN; ++i) {
f[i] = 1LL * f[i - 1] * (pw2[i - 1] + MOD - 1) % MOD;
}
int t; cin >> t;
while (t--) {
int n; cin >> n;
cout << f[n] << endl; // Answer each test case in O(1)
}
```

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.