Detailed mathematical approach

Problem Summary

In a double round-robin with \(n\) teams, each pair meets twice. A win gives \(2\) points, a draw gives \(1\) point to each team, and a loss gives \(0\) points. Let \(F(n)\) be the number of distinct final point multisets, so two outcomes are identified when they differ only by permuting team labels. The task is to compute \(F(100)\) modulo \(10^9+7\).

Mathematical Approach

Write the sorted final scores as

$s_1\le s_2\le \cdots \le s_n,$

and define

$V=4(n-1),\qquad S=2n(n-1).$

The whole problem becomes: count the nondecreasing integer sequences \((s_1,\dots,s_n)\) that can arise from the tournament and whose total sum is \(S\).

Step 1: Encode Each Pair as a 4-Point Split

For each ordered pair of distinct teams \((i,j)\), let \(a_{ij}\) be the total number of points that team \(i\) earns from its two matches against team \(j\). Then

$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$

Every value \(0,1,2,3,4\) is genuinely attainable in two ordinary matches: lose-lose, lose-draw, split or double-draw, draw-win, and win-win. Therefore no information is lost by collapsing the two games between a pair into a single 4-point split.

The total score of team \(i\) is then

$s_i=\sum_{j\ne i} a_{ij},$

so automatically

$0\le s_i\le 4(n-1)=V.$

Step 2: Characterize the Feasible Sorted Score Sequences

Since every unordered pair contributes exactly \(4\) points in total, the global sum is fixed:

$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$

Now look at the \(i\) weakest teams in the sorted list. Their internal matches already contribute

$4\binom{i}{2}=2i(i-1)$

points, so their prefix sum must satisfy

$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$

These inequalities are clearly necessary. The implementations rely on the standard score-sequence characterization for this 4-point pair model: after sorting, the total-sum condition and all prefix lower bounds are also sufficient. Because every integer split from \(0\) to \(4\) can be realized by two actual matches, counting valid score multisets is exactly counting sequences satisfying

$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$

Step 3: Define the Dynamic Programming State

Let \(D_i(v,t)\) be the number of nondecreasing prefixes \((s_1,\dots,s_i)\) such that the last value is \(v\), the prefix sum is \(t\), and every prefix of length at most \(i\) already satisfies the inequality from Step 2.

Equivalently, \(D_i(v,t)\) counts the legal partial score lists of length \(i\) with

$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$

The base layer is

$D_1(v,v)=1\qquad(0\le v\le V),$

because a one-term nondecreasing prefix is determined once its value is chosen. The final total \(S\) is enforced only at the end.

Step 4: Transition by Appending the Next Score

Suppose a legal prefix of length \(i-1\) ends at value \(u\) and has total \(t\). Appending a new value \(v\) keeps the sequence nondecreasing exactly when

$u\le v.$

The new total becomes \(t+v\), and the new prefix of length \(i\) is legal only if the \(i\)-th prefix bound is met:

$t+v\ge 2i(i-1).$

Therefore the recurrence is

$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$

with the understanding that states violating \(t+v\le S\) or the lower bound are discarded.

Step 5: Use Running Prefix Sums

For fixed \(i\) and \(t\), the recurrence asks for many sums of the form \(\sum_{u=0}^{v}D_{i-1}(u,t)\). Those are prefix sums in the variable \(v\), so we can sweep \(v=0,1,\dots,V\) once and maintain

$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t).$

Then

$D_i(v,t+v)=P_{i-1}(v,t).$

This removes an extra factor from the transition cost: each state update becomes \(O(1)\) amortized instead of summing over all smaller last values from scratch.

Step 6: Final Extraction

At the end we only want full score lists whose total sum is exactly \(S\). The last score \(v\) may be anything between \(0\) and \(V\), so the answer is

$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$

This is exactly the quantity accumulated by the program.

Worked Example: \(n=2\)

With two teams there is only one pair, so exactly \(4\) total points are distributed. Here

$V=4,\qquad S=4.$

The sorted score sequences summing to \(4\) are

$ (0,4),\qquad (1,3),\qquad (2,2). $

All three satisfy the prefix condition for \(i=1\), which is trivial. They are also all realizable:

\((0,4)\) comes from two losses by one team, \((1,3)\) comes from one loss and one draw, and \((2,2)\) comes from two draws or one win each. Hence

$F(2)=3,$

matching the small checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations never simulate individual matches. Instead, they count sorted score sequences directly. They precompute the fixed bounds \(V=4(n-1)\) and \(S=2n(n-1)\), then store one dynamic-programming layer for the current prefix length and one for the next prefix length.

Each layer is a flattened table indexed by the last chosen score \(v\) and the current prefix sum \(t\). For every prefix length \(i\), the implementation clears the next layer, computes the lower bound \(2i(i-1)\), and then loops over all possible previous totals \(t\). While scanning \(v=0\) to \(V\), it keeps a running cumulative count of all previous states whose last value is at most \(v\). Whenever the new total \(t+v\) is within range and satisfies the prefix inequality, that cumulative value is written into the next layer. After processing all \(i\), the implementation sums the states whose total is exactly \(S\) and returns the result modulo \(10^9+7\).

Complexity Analysis

Let \(V=4(n-1)\) and \(S=2n(n-1)\). The outer loop runs over \(i=2,\dots,n\), and inside it the implementation scans every pair \((t,v)\) once. Therefore the running time is

$O(nSV)=O(n^4).$

Only two DP layers of size \((V+1)(S+1)\) are stored, so the memory usage is

$O(SV)=O(n^3).$

Footnotes and References

1. Problem page: Project Euler 849
2. Round-robin tournaments: Wikipedia — Round-robin tournament
3. Tournament score sequences: Wikipedia — Tournament (graph theory)
4. Score sequences in graph theory: Wikipedia — Score sequence
5. Dynamic programming: Wikipedia — Dynamic programming