网格

GitHub跳转原题关系图返回列表

按直线的本原方向分类计数,把相邻点距离约束化为指标差下限,再用插空法算组合数,模 1e9 非质数故用杨辉三角。

OJ: roj

题目 ID: 1812

难度:提高+/省选-

标签:数学组合数学计数python

创建: 2026-10-08 06:12

更新: 2026-10-08 06:12

形式化题目

网格区域为 0⩽x⩽W0 \leqslant x \leqslant W、0⩽y⩽H0 \leqslant y \leqslant H,共有 (W+1)(H+1)(W+1)(H+1) 个格点。 从这些格点中选出 NN 个互不相同的点,要求:

  1. 这 NN 个点共线;
  2. 沿这条直线把它们按顺序记为 p1,p2,…,pNp_1, p_2, \dots, p_N,则相邻两点距离满足 ∣pi+1−pi∣⩾D|p_{i+1} - p_i| \geqslant D。

求方案数对 10910^9 取模。多组询问,输入每行四个整数 N,W,H,DN, W, H, D,输出每组一个整数。

注意约束是相邻点之间的距离,不是任意两点;一条直线上相隔较远的点不参与判定。

正解

思路

朴素做法。 从 (W+1)(H+1)(W+1)(H+1) 个格点中枚举所有大小为 NN 的点集,判断共线与距离条件。

瓶颈在哪? W=H=500W=H=500 时格点有 250 001250\,001 个,(25000150)\binom{250001}{50} 是天文数字; 换成"先枚举直线再在线上选点"也一样爆——网格里不同斜率的直线太多。 根因是把点当成主体:一组合法的点必然整体躺在某条直线上,主体应该是直线。

观察一:直线按本原方向分类。 经过至少两个格点的直线,其方向都可以写成最简整点向量 (a,b)(a,b),gcd⁡(a,b)=1\gcd(a,b)=1。无向方向的代表元只取三类:水平 (1,0)(1,0)、竖直 (0,1)(0,1)、斜向 a,b⩾1a,b\geqslant 1。 斜率为 +b+b 与 −b-b 的两族关于 yy 轴对称,方案数完全相同,所以斜向部分算完乘 22; 横竖方向没有这种对称,不能乘 22。

观察二:距离约束等价于指标差。 固定方向 (a,b)(a,b) 后,一条直线上的格点恰好是 p, p+(a,b), p+2(a,b),…p,\ p+(a,b),\ p+2(a,b),\dots 这样的等差数列(因为 (a,b)(a,b) 本原,中间不会有其它格点), 相邻格点距离恒为 a2+b2\sqrt{a^2+b^2}。设 pjp_j 的下标为 iji_j,则 ∣pj+1−pj∣=(ij+1−ij)a2+b2|p_{j+1}-p_j| = (i_{j+1}-i_j)\sqrt{a^2+b^2}, 于是"相邻距离 ⩾D\geqslant D"  ⟺  \iff"相邻下标差 ⩾K\geqslant K",其中

K=min⁡{ k⩾1:k2(a2+b2)⩾D2 }.K = \min\{\,k \geqslant 1 : k^2(a^2+b^2) \geqslant D^2\,\}.

用平方比较求出 KK,全程整数运算:若用 sqrt + ceil,D=2D=2、a2+b2=2\sqrt{a^2+b^2}=2 这类 恰好取整的情形可能因浮点误差被算成 33,直接多算一层。

观察三:插空法数"分段方案"。 设首末两点的下标跨度为 M=iN−i1M = i_N - i_1, 它被切成长度各 ⩾K\geqslant K 的 N−1N-1 段。令 yj=ij−(j−1)(K−1)y_j = i_j - (j-1)(K-1), 就把问题变成"在 M−(N−1)(K−1)+N−2M-(N-1)(K-1)+N-2 个无限制位置上选 N−1N-1 个断点", 即分段方案数为

(M−(N−1)K+N−2N−2)=((M−(N−1)K)+N−2N−2).\binom{M-(N-1)K+N-2}{N-2} = \binom{(M-(N-1)K)+N-2}{N-2}.

观察四:首点位置数只与跨度有关。 固定方向 (a,b)(a,b) 与跨度 MM,首点 pp 必须满足 pp 与 p+M(a,b)p+M(a,b) 同时在网格内,这样的 pp 有

(W+1−Ma) (H+1−Mb)(W+1-Ma)\,(H+1-Mb)

个(Ma>WMa>W 或 Mb>HMb>H 时为 00)。于是固定方向的贡献就是

∑M⩾(N−1)K(M−(N−1)K+N−2N−2)⋅(W+1−Ma) (H+1−Mb).\sum_{M \geqslant (N-1)K} \binom{M-(N-1)K+N-2}{N-2} \cdot (W+1-Ma)\,(H+1-Mb).

枚举范围可以砍掉大半。 由 M⩾(N−1)K⩾N−1M \geqslant (N-1)K \geqslant N-1 且需 Ma⩽WMa \leqslant W、Mb⩽HMb \leqslant H, 斜向只能取 a⩽⌊W/(N−1)⌋a \leqslant \lfloor W/(N-1)\rfloor、b⩽⌊H/(N−1)⌋b \leqslant \lfloor H/(N-1)\rfloor, 比朴素的双重循环 W×HW \times H 小得多,NN 越大收敛越快。

组合数怎么算? 模数 109=29⋅5910^9 = 2^9 \cdot 5^9 不是质数,不能用费马小定理求逆元, 只能用杨辉三角 O(n2)O(n^2) 递推。这里组合数上标不超过 M+N−2⩽W+48M+N-2 \leqslant W+48, 预处理到 560560 就够。注意三个因子相乘会超过 32 位,必须用 64 位中间量并逐步取模。

N=1N=1 特判:只选一个点,共线和平距条件都自动成立,答案为格点数 (W+1)(H+1)(W+1)(H+1)。 (此时 N−2=−1N-2=-1 会使组合数下标非法,必须提前返回。)

样例第 4 组 N=50,W=H=49,D=1N=50, W=H=49, D=1 输出 102102,可以反过来印证"距离约束只作用于相邻点": D=1D=1 时 K=1K=1,即任意 5050 个格点都满足平距要求,答案退化成"网格上共线的 5050 点组数", 50×5050 \times 50 网格里只有 50 条横线、50 条竖线、2 条主对角线能装下 50 点,共 102102。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 06:12
# update_at: 2026-10-08 06:12

import sys
from functools import cache
from math import gcd

MOD = 10 ** 9  # 题面模数,非质数,组合数不能用逆元


@cache
def comb(n: int, k: int) -> int:
    """C(n,k) mod 1e9:模数非质数,用杨辉递推而不是费马小定理。"""
    if k < 0 or k > n:
        return 0
    return 1 if k == 0 else (comb(n - 1, k - 1) + comb(n - 1, k)) % MOD


def count_direction(a: int, b: int, n: int, w: int, h: int, d2: int) -> int:
    """本原方向 (a,b) 贡献的方案数(不含斜率正负对称的 2 倍)。

    直线上的格点按 (a,b) 等距排开,首末点指标跨度为 M 时,把 M 拆成 N-1 段、
    每段至少 k 得 C(M-(N-1)k+N-2, N-2) 种,再乘首点的 (W+1-M*a)*(H+1-M*b) 种位置。
    """
    s2 = a * a + b * b  # 方向向量长度的平方
    k = 1
    while k * k * s2 < d2:  # 整数判定最小步长,避开 sqrt 的浮点误差
        k += 1
    base = (n - 1) * k  # 跨度 M 的下界:N-1 段每段至少 k

    if a == 0:
        max_m = h // b  # 纯竖直方向,只受 y 跨度限制
    elif b == 0:
        max_m = w // a  # 纯水平方向,只受 x 跨度限制
    else:
        max_m = min(w // a, h // b)

    return sum(
        comb(m - base + n - 2, n - 2) * (w + 1 - m * a) * (h + 1 - m * b)
        for m in range(base, max_m + 1)
    ) % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)
    for _ in range(T):
        n, w, h, d = next(data), next(data), next(data), next(data)
        if n == 1:  # 只选一个点:任取一个格点
            out.append(str((w + 1) * (h + 1) % MOD))
            continue
        d2, span = d * d, n - 1
        ans = count_direction(1, 0, n, w, h, d2) + count_direction(0, 1, n, w, h, d2)
        # 斜向要有解必须 M >= span 且 M*a <= w、M*b <= h,故 a <= w//span、b <= h//span
        ans += 2 * sum(
            count_direction(a, b, n, w, h, d2)
            for a in range(1, w // span + 1)
            for b in range(1, h // span + 1)
            if gcd(a, b) == 1  # 只取本原方向,避免同一斜率重复计数
        )
        out.append(str(ans % MOD))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 06:12
 * update_at: 2026-10-08 06:12
 */
// 1812《网格》正解
// 题意:网格 [0,W]x[0,H] 的 (W+1)(H+1) 个格点里选 N 个互不相同的点,要求它们共线,
//       并且沿这条直线相邻两点的欧氏距离 >= D,求方案数 mod 1e9。
// 做法:按直线的“本原方向”分类计数。方向 (1,0)、(0,1) 各算一次;斜率 +b 与 -b 关于
//       y 轴对称、方案数相同,所以 a,b>=1 的部分算好后乘 2。
//       固定本原方向 (a,b) 后,直线上的格点按 (a,b) 等距排开,相邻格点距离为
//       sqrt(a^2+b^2),于是“相邻距离 >= D”等价于“指标差 >= K”,
//       K = 最小的正整数使 K^2*(a^2+b^2) >= D^2(用整数平方判定,不用 sqrt)。
//       设首末两点的指标跨度 M:把 M 拆成 N-1 段、每段 >= K 的方案数是
//       C(M-(N-1)K+N-2, N-2);首点 p 的取法数为 (W+1-M*a)*(H+1-M*b)。
//       对所有 M 累加即该方向贡献。N=1 时答案直接是格点数。
// 说明:模数 1e9 不是质数,组合数只能用杨辉三角递推,不能用逆元。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll MOD = 1000000000LL; // 题面模数,非质数,不能靠费马小定理求逆元
const int MAX_UP = 560;      // 组合数上标上限:M <= W <= 500,再加 N-2 <= 48
const int MAX_LO = 50;       // 组合数下标上限:N-2 <= 48

ll comb_tab[MAX_UP + 1][MAX_LO + 1]; // comb_tab[i][j] = C(i,j) mod 1e9(杨辉三角)

// 手写 gcd,避免 __gcd(libstdc++ 专有)在其它标准库下不可用
ll gcd_ll(ll x, ll y) {
    while (y) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

// 本原方向 (a,b)(a,b >= 0 且不同时为 0)贡献的方案数,不含斜率正负对称的 2 倍。
ll count_direction(ll a, ll b, ll n, ll w, ll h, ll d2) {
    ll s2 = a * a + b * b;         // 方向向量长度的平方
    ll k = 1;
    while (k * k * s2 < d2) k++;   // 最小步长(整数判定,避开浮点误差)
    ll base = (n - 1) * k;         // 首末点跨度 M 的下界:N-1 段每段至少 k
    ll max_m = base - 1;           // 上界先给一个必然空集的值
    if (a == 0) max_m = h / b;     // 纯竖直方向,只受 y 跨度限制
    else if (b == 0) max_m = w / a; // 纯水平方向,只受 x 跨度限制
    else max_m = min(w / a, h / b);
    ll res = 0;
    for (ll m = base; m <= max_m; m++) {
        // 把跨度 m 拆成 N-1 段(每段 >= k)的方案数,乘首点可选位置数
        ll ways = comb_tab[m - base + (n - 2)][n - 2];
        res = (res + ways * (w + 1 - m * a) % MOD * (h + 1 - m * b)) % MOD;
    }
    return res;
}

int main() {
    for (int i = 0; i <= MAX_UP; i++) { // 杨辉三角预处理组合数
        comb_tab[i][0] = 1;
        for (int j = 1; j <= min(i, MAX_LO); j++)
            comb_tab[i][j] = (comb_tab[i - 1][j - 1] + comb_tab[i - 1][j]) % MOD;
    }
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        ll n, w, h, d;
        scanf("%lld %lld %lld %lld", &n, &w, &h, &d);
        if (n == 1) { // 只选一个点:任取一个格点
            printf("%lld\n", (w + 1) * (h + 1) % MOD);
            continue;
        }
        ll d2 = d * d;
        ll ans = count_direction(1, 0, n, w, h, d2) + count_direction(0, 1, n, w, h, d2);
        ll span = n - 1; // 斜向要有解必须 M >= span,于是 a <= w/span、b <= h/span
        for (ll a = 1; a <= w / span; a++)
            for (ll b = 1; b <= h / span; b++)
                if (gcd_ll(a, b) == 1) // 只取本原方向,避免同一斜率重复计数
                    ans = (ans + 2 * count_direction(a, b, n, w, h, d2)) % MOD;
        printf("%lld\n", ans % MOD);
    }
    return 0;
}

复杂度

  • 时间:组合数预处理 O(W2)O(W^2)(可提到询问外只做一次)。单组询问中,斜向枚举的本原 方向对数约为 6π2⋅WN−1⋅HN−1\frac{6}{\pi^2} \cdot \frac{W}{N-1} \cdot \frac{H}{N-1},每个方向上的 累加项数为 min⁡(W/a,H/b)\min(W/a, H/b) 级别;N=50N=50 顶格时枚举量极小,最坏是 N=2,W=H=500N=2, W=H=500, 实测 0.11 s(限时 1000 ms,T⩽20T \leqslant 20)。
  • 空间:只有一张 561×51561 \times 51 的组合数表,O(W⋅N)O(W \cdot N),不足 1 MB(限 128 MB)。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一个算法,差别只在实现: Python 用 @cache 递归求组合数,C++ 用杨辉三角打表;两者都避免浮点、避免逆元。 Python 在 N=2N=2 顶格数据上约 2 s,属于该数据点的最坏情形,接受 TLE 风险。

正确性

  • 不重不漏:任意合法点集共线,其所在直线的本原方向 (a,b)(a,b) 唯一(±\pm 号已在分类时 合并),首末点跨度 MM 与其下标差唯一,故该方案被且仅被"方向 (a,b)(a,b) + 跨度 MM + 首点 pp"这一组参数计一次。
  • 条件等价:直线上的格点构成步长为 (a,b)(a,b) 的等差序列,(a,b)(a,b) 本原保证中间无其它格点, 所以相邻点距离公式成立,KK 的取值由整数平方判定唯一确定。
  • 组合数正确:分段方案数是标准插空法的结果,MM 的下界 (N−1)K(N-1)K 保证每段非空且达标。

总结

  • 换主体:点集不好枚举,但"一组共线点"整体躺在一条直线上,于是把计数主体从点集 换成"直线方向 + 跨度 + 首点",这是本题从 O((WHN))O(\binom{WH}{N}) 跳到多项式复杂度的关键。
  • 几何约束代数化:本原方向上的格点是等距等差数列,"距离 ⩾D\geqslant D"直接变成 “下标差 ⩾K\geqslant K”,几何问题降维成组合问题。
  • 插空法:∑M\sum_{M} 里那一项 (M−(N−1)K+N−2N−2)\binom{M-(N-1)K+N-2}{N-2} 就是"把跨度切成 N−1N-1 段、 每段 ⩾K\geqslant K"的标准计数,写题时把变量替换写清楚比死记公式更可靠。
  • 模数不是质数就不能用逆元:看到 10910^9 要立刻想到它 =29⋅59=2^9 \cdot 5^9,组合数必须 递推打表;这类"模数陷阱"在计数题里出现频率很高。
  • 精确整数判定:⌈D/a2+b2⌉\lceil D/\sqrt{a^2+b^2}\rceil 一律改写成 k2(a2+b2)⩾D2k^2(a^2+b^2) \geqslant D^2,是本题最容易写错的一个细节。

备注

本题素材源(new_ROJ/problems/1812/)带自造数据生成脚本 data.py:10 个测试点由 std.cpp 跑出(含手算校验的退化网格点、顶格点、样例复现点),题面来源标注为 “信息学奥赛一本通 · 高手训练篇 · 六、数学基础”。本仓库 main.cpp / main.py 是按题面 独立实现后与这 10 组数据逐点比对的,10/10 一致;题面与官方原题的表述可能有细微偏差, 以题面给出的 6 组样例为准。