Project Euler 849

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

Project Euler 849

题目

The Tournament

In a tournament there are \(n\) teams and each team plays each other team twice. A team gets two points for a win, one point for a draw and no points for a loss.

With two teams there are three possible outcomes for the total points. \((4,0)\) where a team wins twice, \((3,1)\) where a team wins and draws, and \((2,2)\) where either there are two draws or a team wins one game and loses the other. Here we do not distinguish the teams and so \((3,1)\) and \((1,3)\) are considered identical.

Let \(F(n)\) be the total number of possible final outcomes with \(n\) teams, so that \(F(2) = 3\).

You are also given \(F(7) = 32923\).

Find \(F(100)\). Give your answer modulo \(10^9+7\).

解决方案

任取两队 \(X,Y\)。两场比赛的总得分一定是 \(4\)（每场总得分 \(2\)，两场共 \(4\)）。并且 \(X\) 在两场中能拿到的总分恰好可以是\(0,1,2,3,4\) （例如：两负得 \(0\)，负+平得 \(1\)，双平或胜负各一得 \(2\)，胜+平得 \(3\)，两胜得 \(4\)）。因此对每一对队伍 \(\{X,Y\}\)，最终只需要知道“这 \(4\) 分如何在两端分配”，也就是一个整数 \(t\in\{0,1,2,3,4\}\)： \(X\) 得 \(t\)，\(Y\) 得 \(4-t\)。

所以本题等价于：在完全图每条边上，把固定总量 \(4\) 的分数分给两端（允许 \(0\sim 4\) 任意分配），问所有可能的最终总分多重集合数。将这一类问题记为 \(F_j(n)\)：每一对的总分固定为 \(j\)，端点分配为 \(0\sim j\)。本题就是\(F(n)=F_4(n).\)

对一般的 \(F_j(n)\)，设普通生成函数\(\displaystyle\mathcal F_j(x)=\sum_{n\ge 0}F_j(n)x^n, F_j(0)=1.\)定义\(\displaystyle\mathcal G_j(x)=x\frac{\mathcal F_j'(x)}{\mathcal F_j(x)}=\sum_{k\ge1} G_j(k)x^k\)（也就是\(\displaystyle \log \mathcal{F}_j(x)=\sum_{k\ge1} \dfrac{G_j(k)}{k}x^k\)）。 比较系数可得（把 \(\mathcal F_j'(x)\) 展开后逐项对齐）：\(\displaystyle nF_j(n)=\sum_{k=1}^n F_j(n-k)G_j(k),\)即

\[ F_j(n)=\frac{1}{n}\sum_{k=1}^n F_j(n-k)G_j(k),(n\ge1). \]

对任意 \(j\ge1\)，论文给出：

\[ G_j(k)=\frac{1}{(j+1)k}\sum_{d\mid k}(-1)^{(k-d)j}\varphi\left(\frac{k}{d}\right)\binom{(j+1)d}{d}. \]

本题 \(j=4\) 为偶数，符号恒为 \(+1\)，因此可简化为

\[ G_4(k)=\frac{1}{5k}\sum_{d\mid k}\varphi\left(\frac{k}{d}\right)\binom{5d}{d}. \]

由此回代，即可得到\(F_4\)的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
N = 100
MOD = 10 ** 9 + 7

def phi_sieve(n):
    phi = [0] * (n + 1)
    primes = []
    is_comp = [False] * (n + 1)
    if n >= 1:
        phi[1] = 1
    for i in range(2, n + 1):
        if not is_comp[i]:
            primes.append(i)
            phi[i] = i - 1
        for p in primes:
            v = i * p
            if v > n:
                break
            is_comp[v] = True
            if i % p == 0:
                phi[v] = phi[i] * p
                break
            phi[v] = phi[i] * (p - 1)
    return phi

def solve(n):
    phi = phi_sieve(n)
    m = 5 * n
    fac = [1] * (m + 1)
    for i in range(1, m + 1):
        fac[i] = fac[i - 1] * i % MOD
    ifac = [1] * (m + 1)
    ifac[m] = pow(fac[m], MOD - 2, MOD)
    for i in range(m, 0, -1):
        ifac[i - 1] = ifac[i] * i % MOD

    binom = [0] * (n + 1)
    for d in range(1, n + 1):
        binom[d] = fac[5 * d] * ifac[4 * d] % MOD * ifac[d] % MOD

    inv = [0] * (n + 1)
    for i in range(1, n + 1):
        inv[i] = pow(i, MOD - 2, MOD)
    inv5 = pow(5, MOD - 2, MOD)

    G = [0] * (n + 1)
    for d in range(1, n + 1):
        bd = binom[d]
        for t in range(1, n // d + 1):
            k = d * t
            G[k] = (G[k] + phi[t] * bd) % MOD
    for k in range(1, n + 1):
        G[k] = G[k] * inv5 % MOD * inv[k] % MOD

    F = [0] * (n + 1)
    F[0] = 1
    for i in range(1, n + 1):
        s = 0
        for k in range(1, i + 1):
            s = (s + F[i - k] * G[k]) % MOD
        F[i] = s * inv[i] % MOD
    return F[n]
print(solve(N))