C.1 = (sum(1/(i*(i+1))) where 1<=i<=n-1 ) + 1/n. But it doesnot work in some cases, (where n = k(k-1)). You must fix this.

congratulations

I also submitted B in like the last 10 mins, got AC× 11,WA × 3,TLE × 25. got pretty devastated.

"Well-known in China" moment

I am not quite confident, but I find that for n=6, your output is not correct.

I think you should construct a solution for n-2 in the special case(where N=i*(i+1)) and then replace the largest number x in that solution by 2x,3x and 6x.

Edu was first written in Japanese and then they were translated through GPT.

two pointers

My understanding of the editorial:

SCCs (s1, s2, ... , sk) form a DAG.

Let's arrange these SCCs so that iff i < j, then s_i is topologically earlier than s_j. With such an arrangement there may not be any edge from sj to si, if j > i, as that would lead to a contradiction (as sj is later in topological order).

Note, that as it's a tournament, there exists a single topological ordering of the SCCs, as there is always a directed edge between any pair of vertices.

So we can safely divide SCCs into sets A = { s1, s2, ..., si }, B = { si+1, si+2, ..., sk}, so that they meet the conditions. And there will be exactly K+1 such divisions into two sets of SCCs as we can choose any i in range [ 0, k ].

s1,s2,...,sk form a strongly connected component

Here is the misunderstanding. According to the editorial, (s1,s2,...,sk) do not FORM a strongly connected component. (s1, s2, ..., sk) ARE LABELS for all the strongly connected components in the graph.

I did something different, although I didnt manage to debug and AC within contest.

Basically, my dp state was dp[n][cc][m] = how many different graphs of n vertices have cc connected components and m edges from small to big. Once u have that its just simple math.

The transition then is take k vertices to form the 1st CC in the DAG, suppose it has m1 s->b edges, and suppose the 1st CC to the rest of the CC have m2 s->b edges and the remaining CC-1 components have the rest (m — m1 — m2 edges). If you get the 3 parts, you can just multiply all 3 and add to dp[n][cc][m]. So ull add something like (ways to pick k vertices with m2 as described above)*dp[k][1][m1]*dp[n-k][cc-1][m- m1 — m2]

Also u cant compute dp[n][1][m] directly, but you can get it via C(n*(n-1)/2, m) — dp[n][2][m] — dp[n][3][m] — etc. (Or maybe there is a combinatorial argument that eludes me)

For the ways to choose the k vertices, basically its the number of multisets such that k numbers from 0 to (n-k) such that it add up to m2. (You can write a dp for that, I dont know of a formula, bars and stars is ordered which is not what we want)

Depending on how u do it, it can take very long (like O(n^10)), but what I realised after the contest was that by reordering the loops, u can do convolution on the results of the 3 parts to get the result fast, instead of having 3 for loops (which is O(n^6)) and reduce to just O(n^4) or O(n^2logn) with NTT. Link: https://atcoder.jp/contests/arc163/submissions/43206412

My code (according to the editorial):

//Problem: https://atcoder.jp/contests/arc163/tasks/arc163_d
//Editorial: https://atcoder.jp/contests/arc163/editorial/6729
//Time: 154ms
//Memory: 7664 KB

#define ATCODER 0
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#define fastio cin.tie(0) -> sync_with_stdio(0)
#define DEBUG 0

void debug(const char* p){
    #if DEBUG
    freopen(p, "r", stdin); 
    #else
    fastio;
    #endif      
} 

//jiangly Codeforces
int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm((int)(x % P))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

Z dp[32][32][1000];
int main(void){
    debug("test1.txt");
    int n, m;
    cin >> n >> m;
    dp[0][0][0] = 1;
    comb.init(n);
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= i; ++j){
            for(int k = 0; k <= m; ++k){
                for(int t = 0; t <= j && k + t <= m; ++t){
                    dp[i+1][j+1][k+t] += dp[i][j][k] * comb.binom(j, t);
                }
                for(int t = 0; t <= i - j && k + t <= m; ++t){
                    dp[i+1][j][k+j+t] += dp[i][j][k] * comb.binom(i-j, t);
                }
            }
        }
    }
    Z ans = -comb.binom(n*(n-1)/2, m);
    for(int j = 0; j <= n; ++j){
        ans += dp[n][j][m];
    }
    cout << ans << "\n";
}

link please

long double has accuracy upto 18 digits, right? and we need accuracy upto 9 digits for numbers between 1 and 1e9.

modulo hash fractions should work

Note that the sum $$$1/a_1 + 1/a_2 + \dots + 1/a_n$$$ can have a denominator of about $$$(10^9)^n$$$, so it can be super close to $$$1$$$, while not being $$$1$$$ exactly.

The bounds are low, so the checker can just calculate the exact fraction using big number arithmetic. It will only need the plus and times operations on bignums, and use those bignums in a fractions struct. It can be implemented without that much pain in C++. (If it is possible, I would do it with Python.)

A fast way to do it is divide and conquer. So calculate the exact fractional sum for the left halve and right halve of the array, then add those two. This ensures most additions of fractions are done on small fractions, and only the last few additions are really done on really big fractions.

In that case, at least one of the endpoints will have to be modified (either the lower bound (a[0]) is greater than the minimum element or the upper bound (a[1]) is smaller than the maximum element for any elements in a[2..n]). The core of the solution does not change in this case.