As you know, a group of programmers cannot stop talking about problems for more than $$$2$$$ hours, so today at the HSSE Night League, we tried to solve the following problem:
It is necessary to count how many different graphs exist that satisfy the following conditions modulo $$$998244353$$$:
The graph has $$$n \le 2000$$$ vertices
The graph is connected
All edges are distinct and connect different vertices
There is exactly one vertex in the graph that is connected to all other vertices (hereinafter referred to as the special vertex)
The solution is not the most obvious and did not come to me immediately. I was able to solve this problem in $$$O(\frac{n^3}{4})$$$, using which you can precompute the answers for each $$$n$$$. This is probably not the most optimal solution, so I would be glad if someone in the comments suggests a faster solution.
So, the solution. First, we remove our special vertex. Now we need to count how many graphs of $$$n-1$$$ vertices exist where there are no vertices connected to all others, and then multiply this value by $$$n$$$ — this will be the desired quantity. We multiply by $$$n$$$ because the "special" vertex could have been any of the $$$n$$$ original vertices.
We will solve the problem using dynamic programming. We will need $$$2$$$ dimensions: $$$dp[i][j]$$$ — the number of graphs with $$$i$$$ vertices and $$$j$$$ special vertices.
Base case:
$$$dp[0][0] = 1$$$. There is only one empty graph.
Transitions:
Let’s assume we have calculated all $$$dp[i-1]$$$. Recalculating $$$dp[i]$$$ using $$$dp[i-1]$$$ is the same as adding a vertex to a graph with $$$i-1$$$ vertices and connecting edges to the new vertex.
Next, consider $$$3$$$ cases:
The number of special vertices has increased, which means we connected the new vertex to all added vertices. The first transition is $$$dp[i][j] \mathrel{+}= dp[i-1][j-1]$$$ for all $$$1 \le j \le n-1$$$.
The number of special vertices remained the same. This means the new vertex is connected to all "special" vertices and to some of the others (but not all, so the number of ways to do this is $$$2^{i - 1 - j}-1$$$). Hence the transition is $$$dp[i][j] \mathrel{+}= dp[i-1][j] \times (2^{i - 1 - j}-1)$$$.
The number of special vertices decreased. Suppose there were $$$k$$$ of them, $$$k > j$$$. It turns out that we connected the new vertex to some $$$j$$$ of those $$$k$$$ (there are $$$\binom{k}{j}$$$ ways to do this), and to some of the others ($$$2^{i - 1 - j}$$$ ways to do this). We get the last transition $$$dp[i][j] \mathrel{+}= dp[i-1][k] \times 2^{i - 1 - k} \times \binom{k}{j}$$$.
$$$\newline$$$
