Interested because there is no such option at "propose contest" section

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$$$

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

#define int long long
#define double long double
#define endl "\n"

ostream& operator << (ostream& out, pair<int, int> a) {
    out << "| " << a.first << " " << a.second << " |";
    return out;
}

template<typename T>
istream& operator >> (istream& in, vector<T>& a) {
    for (int i = 0; i < a.size(); i++) in >> a[i];
    return in;
}

template<typename T>
ostream& operator << (ostream& out, vector<T>& a) {
    for (int i = 0; i < a.size(); i++) out << a[i] << " ";
    return out;
}

mt19937 rn(52);
int rnd() {return abs((int) rn());}

constexpr int N = 2e3 + 556;
constexpr int mod = 998244353;
constexpr long long inf = 1e16 + 556;
constexpr int T = 30;
constexpr int A = 1e6 + 1;
const double pi = acos(-1);

int fact[N], invfact[N];

int bpow(int a, int p) {
    if (p == 0) return 1;
    if (p & 1) return (a * bpow(a, p - 1)) % mod;
    return bpow((a * a) % mod, p >> 1);
}

int cnk(int n, int k) {
    int ans = (fact[n] * invfact[k]) % mod;
        ans = (ans * invfact[n - k]) % mod;
    return ans;
}

int pw[N];

void talentless() {
    int n;
    cin >> n;
    vector<vector<int>> dp(n, vector<int> (n, 0));
    dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            if (j) dp[i][j] = dp[i - 1][j - 1];

            for (int k = j; k < i; k++) {
                int ext = pw[i - 1 - k];
                if (k == j) ext = (ext - 1 + mod) % mod;
                
                dp[i][j] += (dp[i - 1][k] * cnk(k, j) % mod) * ext % mod;
                dp[i][j] %= mod;
            }
        }
    }
    
    cout << (dp[n - 1][0] * n) % mod << endl;
}

signed main() {
    int tests = 1;

#ifdef LOCALIC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> tests;
#else
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
#endif

    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % mod;
    invfact[N - 1] = bpow(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) invfact[i] = (invfact[i + 1] * (i + 1)) % mod;

    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = (pw[i - 1] + pw[i - 1]) % mod;

    while (tests --> 0) talentless();
}

Решая курс по подготовке к выпускным экзаменам, я столкнулся со следующей задачей: $$$\newline$$$ Даны $$$n$$$ коробок, каждая длиной $$$a_i$$$. Мы можем вкладывать одну коробку в другую, если размер внутренней хотя бы на 7 единиц меньше внешней, при этом в каждую коробку не могла быть вложена только одна другая, а также какждая коробка может быть вложена максимум в одну другую. Множество коробок, вложенных друг в друга, назовем блоком. В задаче просят расположить коробки так, чтобы минимизировать количество блоков. $$$\newline$$$ Очевидно, данную задачу можно решать следующим образом (и это решение точно будет правильным): строим граф, в котором будет ребро $$$i \rightarrow j$$$, если $$$a_i - 7 \ge a_j$$$, данный граф очевидно не будет иметь циклов. Теперь блок из вложенных друг в друга коробок будет выглядеть как какой-то путь в данном графе, значит, минимизировать количество блоков, это то же самое, что разбить данный граф на минимальное количество непересекающихся по вершинам путей. Это довольно известная задача, например тут описывается ее решение. $$$\newline$$$ Тем не менее, авторы задачи предлагают несколько другое, гораздо более простое решение: перебирать коробки по убыванию $$$a_i$$$, поддерживая множество блоков, для каждого из которых храним размер последней вложенной в него коробки, и пытаться жадно вложить текущую коробку в какой-нибудь блок. Если вложить никуда нельзя, то сделать новый блок, состоящий только из этой коробки. $$$\newline$$$ Данное решение интуитивно кажется мне некорректным, однако контртест я не смог придумать. К тому же, если данный жадник работает, любую задачу о покрытии графа путями можно сводить к задаче о коробках, после чего решать ее за $$$O(n \log n)$$$ вместо долгого решения паросочетаниями (а это бред какой-то). Буду благодарен, если кто-то подскажет, в чем проблема данного жадника и приведет контртест к нему.