Project Euler 554

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

Project Euler 554

题目

Centaurs on a chess board

On a chess board, a centaur moves like a king or a knight. The diagram below shows the valid moves of a centaur (represented by an inverted king) on an \(8\times8\) board.

It can be shown that at most \(n^2\) non-attacking centaurs can be placed on a board of size \(2n\times2n\).

Let \(C(n)\) be the number of ways to place \(n^2\) centaurs on a \(2n\times2n\) board so that no centaur attacks another directly.

For example \(C(1)=4, C(2)=25, C(10)=1477721\).

Let \(F_i\) be the \(i^{\text{th}}\) Fibonacci number defined as \(F_1=F_2=1\) and \(F_i=F_{i-1}+F_{i-2}\) for \(i>2\).

Find \(\displaystyle \left( \sum_{i=2}^{90} C(F_i) \right) \text{mod } (10^8+7)\).

解决方案

令\(p=10^8+7\)，可见\(p\)是一个质数。

我们把 \(2n \times 2n\) 棋盘划分为 \(n \times n\) 个 \(2\times2\) 小块。同一 \(2\times2\) 内任意两格王步可达，所以一个 \(2\times2\) 至多放 1 个半人马。总共 \(n^2\) 个块，因此最多 \(n^2\) 个半人马。当达到最大值 \(n^2\) 时，每个 \(2\times2\) 必须恰好放 1 个。

于是每个块只剩 4 种类型：UL, UR, DL, DR（分别表示该块内半人马位于左上、右上、左下、右下）。

以 UR 为例（其余对称）：若某块是 UR，则其右、上、右上三个相邻块只能是 UR，否则会被该块半人马直接攻击到。对全部块施加这个规则后，已经足够保证全局无攻击（可逐相对位移检查）。这意味着每种类型在块网格上形成角落闭包区域。

记 \(B = \dbinom{2n}{n}\)。那么考虑以下5种情况：

  • 只出现 1 种类型。这类情况显然有 \(N_A=4\) 种。
  • 恰好 2 种，且互为对角（例如 UR 与 DL）。两类之间边界是一条从左上到右下的单调路径（\(n\) 次向右 + \(n\) 次向下），共 \(B\) 条。要求两类都出现，去掉两条极端路径（全 UR / 全 DL），得 \(B-2\)。对角对有 \(2\) 组，所以：\(N_B = 2(B-2).\)
  • 恰好 2 种，且相邻（例如 UL 与 DL）。这时只能被一条水平分界线切开，位置有 \(n-1\) 种。相邻对共有 4 组，所以：\(N_C = 4(n-1).\)
  • 恰好 3 种（例如缺 DR，即有 UL,UR,DL）。由局部不攻击约束可推出：UL 区域必须是贴左上的一个矩形，设尺寸为 \(a\times b\)，且三类都要出现，所以 \(1\le a,b\le n-1\)。去掉这个矩形后，右下剩余区域只含 UR 和 DL，它们的分界是一条从左上到右下的单调路径。若剩余区域尺寸为 \(x\times y\)（\(x=n-b,y=n-a\)），该路径条数是 \(\dbinom{x+y}{y}\)。对所有 \(x,y\in[1,n-1]\) 求和，就得到\(\displaystyle S_1=\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}\binom{x+y}{y}.\)

再证恒等式：

\[ \begin{aligned} S_1 &=\sum_{x=1}^{n-1}\left(\sum_{y=1}^{n-1}\binom{x+y}{y}\right) \\ &=\sum_{x=1}^{n-1}\left(\binom{x+n}{n-1}-1\right) \\ &=\left(\sum_{t=n+1}^{2n-1}\binom{t}{n-1}\right)-(n-1) \\ &=\bigl(\binom{2n}{n}-(n+1)\bigr)-(n-1) \\ &= \binom{2n}{n}-2n. \end{aligned} \]

那么缺失类型有 4 种：\(N_D = 4(B-2n).\)

  • 4 种都出现。先只数一种结构：UL 在左上角闭包、DR 在右下角闭包；中间由 UR 与 DL 分割。（另一种对角结构 UR/ DL 最后再对称处理。）在这种固定结构下，会有一条把 UR 与 DL 分开的单调边界路径（只会“向右/向下”）。令\(x\)表示这条路径中“向右”步数，\(y\)表示这条路径中“向下”步数。则固定 \(x,y\) 时，路径条数是\(\dbinom{x+y}{y}.\)

这条路径被包含在一个最小“活动窗口”里，窗口宽 \(x+1\)、高 \(y+1\)。该窗口在 \(n\times n\) 网格中可平移放置的方式数为\((n-1-x)(n-1-y).\)由于四种类型都要出现，\(x,y\) 取值必须使两方向都留有角区，范围是\(x,y=0,1,\dots,n-2.\)于是得到（固定这一种对角主结构时）的计数：

\[ T=\sum_{x=0}^{n-2}\sum_{y=0}^{n-2}(n-1-x)(n-1-y)\binom{x+y}{y}. \]

利用\(\displaystyle (n-1-x)(n-1-y)=\sum_{i=0}^{n-2-x}\sum_{j=0}^{n-2-y}1\)换序后可化到双重求和\(\displaystyle \sum_{u=1}^{n-1}\sum_{v=1}^{n-1}\binom{u+v}{u}\)，最终得到

\[ T=\binom{2n}{n}-(n^2+1). \]

四型出现有两种对角主分解（UL/DR 或 UR/DL），先乘 2；但纯四角矩形切分的重叠被算了两次，重叠数为 \((n-1)^2\)。故\(N_E = 2T-(n-1)^2=2(B-(n^2+1))-(n-1)^2.\)

最终有：

\[ \begin{aligned} C(n) &=N_A+N_B+N_C+N_D+N_E \\ &=4+2(B-2)+4(n-1)+4(B-2n)+2(B-(n^2+1))-(n-1)^2 \\ &=8B-(3n^2+2n+7)\\ &=8\binom{2n}{n}-(3n^2+2n+7) \end{aligned} \]

我们的目标是计算\(\displaystyle \sum_{i=2}^{90} C(F_i)\bmod p.\)为了计算大整数的组合数，将介绍所使用的技术。

我们把\(\displaystyle n=\sum_{k\ge 0} n_k p^k, 0\le n_k<p\)写成 \(p\) 进制。

由 Lucas 定理可知，有\(\displaystyle \binom{2n}{n}\equiv \prod_k \binom{(2n)_k}{n_k}\pmod p.\)

由 Kummer 定理可知，\(p\) 在 \(\dbinom{2n}{n}\) 中的指数，等于把 \(n+n\) 按 \(p\) 进制相加时产生的进位数。因此： 若存在进位，则\(\binom{2n}{n}\equiv 0\pmod p;\)若不存在进位，则每一位满足\((2n)_k=2n_k.\)

对二倍加法来说，无进位等价于\(n_k\le \dfrac{p-1}{2},(\forall k\ge 0),\)即一旦某位\(n_k\ge \dfrac{p+1}{2},\)就必有进位，从而结果为 \(0\)。

所以最终可写成分段形式：

\[ \binom{2n}{n}\equiv \begin{cases} 0, & \exists k:\ n_k\ge \dfrac{p+1}{2},\\ \displaystyle\prod_k \binom{2n_k}{n_k}\pmod p, & \text{othewise}. \end{cases} \]

这说明我们只需预处理小范围中央二项式\(\dbinom{2d}{d}, \left(0\le d\le \dfrac{p-1}{2}\right),\) 随后对每个 \(n\) 做按位乘积即可。

代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from array import array

M = 90
MOD = 100000007
N = (MOD - 1) // 2
HALF = (MOD + 1) // 2

def fibs(M):
    f = [1, 1]
    for i in range(2, M):
        f.append(f[-1] + f[-2])
    return f[1:]

def no_carry_double(n):
    while n:
        if n % MOD >= HALF:
            return False
        n //= MOD
    return True

def add_digits(s, n):
    if n == 0:
        s.add(0)
        return
    while n:
        s.add(n % MOD)
        n //= MOD

def precompute_digit_choose2(need_digits):
    k_need = sorted({min(d, N - d) for d in need_digits})
    kmax = k_need[-1]

    inv = array('I', [0]) * (kmax + 1)
    if kmax >= 1:
        inv[1] = 1
    m = MOD
    for i in range(2, kmax + 1):
        inv[i] = (m - (m // i) * inv[m % i] % m) % m

    chooseNk = {0: 1}
    g = 1
    p = 1
    for k in range(1, kmax + 1):
        g = g * (N - k + 1) % m
        g = g * inv[k] % m
        if p < len(k_need) and k == k_need[p]:
            chooseNk[k] = g
            p += 1

    out = {}
    for d in need_digits:
        k = d if d <= N - d else N - d
        out[d] = pow(-4, d, m) * chooseNk[k] % m
    return out

def choose2_big(n, digit_choose2):
    ds = []
    while n:
        d = n % MOD
        ds.append(d)
        if d >= HALF:
            return 0
        n //= MOD
    ans = 1
    for d in ds:
        ans = ans * digit_choose2[d] % MOD
    return ans

def C(n, digit_choose2):
    z = n % MOD
    return (8 * choose2_big(n, digit_choose2) - (3 * z * z + 2 * z + 7)) % MOD

def solve(M):
    ques = fibs(M)
    need_digits = {0}
    for n in ques:
        if no_carry_double(n):
            add_digits(need_digits, n)
    for t in (1, 2, 10):
        add_digits(need_digits, t)
    digit_choose2 = precompute_digit_choose2(need_digits)
    ans = 0
    for n in ques:
        ans = (ans + C(n, digit_choose2)) % MOD
    return ans

print(solve(M))