按直线的本原方向分类计数,把相邻点距离约束化为指标差下限,再用插空法算组合数,模 1e9 非质数故用杨辉三角。
OJ: roj
题目 ID: 1812
难度:提高+/省选-
标签:数学组合数学计数python
创建: 2026-10-08 06:12
更新: 2026-10-08 06:12
形式化题目
网格区域为
- 这
个点共线; - 沿这条直线把它们按顺序记为
,则相邻两点距离满足 。
求方案数对
注意约束是相邻点之间的距离,不是任意两点;一条直线上相隔较远的点不参与判定。
正解
思路
朴素做法。 从
瓶颈在哪?
观察一:直线按本原方向分类。 经过至少两个格点的直线,其方向都可以写成最简整点向量
观察二:距离约束等价于指标差。 固定方向
用平方比较求出 sqrt + ceil,
观察三:插空法数"分段方案"。 设首末两点的下标跨度为
观察四:首点位置数只与跨度有关。 固定方向
个(
枚举范围可以砍掉大半。 由
组合数怎么算? 模数
样例第 4 组
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:组合数预处理
(可提到询问外只做一次)。单组询问中,斜向枚举的本原 方向对数约为 ,每个方向上的 累加项数为 级别; 顶格时枚举量极小,最坏是 , 实测 0.11 s(限时 1000 ms, )。 - 空间:只有一张
的组合数表, ,不足 1 MB(限 128 MB)。 - 与 C++ 解法的关系:
main.py与main.cpp是同一个算法,差别只在实现: Python 用@cache递归求组合数,C++ 用杨辉三角打表;两者都避免浮点、避免逆元。 Python 在顶格数据上约 2 s,属于该数据点的最坏情形,接受 TLE 风险。
正确性
- 不重不漏:任意合法点集共线,其所在直线的本原方向
唯一( 号已在分类时 合并),首末点跨度 与其下标差唯一,故该方案被且仅被"方向 + 跨度 + 首点 "这一组参数计一次。 - 条件等价:直线上的格点构成步长为
的等差序列, 本原保证中间无其它格点, 所以相邻点距离公式成立, 的取值由整数平方判定唯一确定。 - 组合数正确:分段方案数是标准插空法的结果,
的下界 保证每段非空且达标。
总结
- 换主体:点集不好枚举,但"一组共线点"整体躺在一条直线上,于是把计数主体从点集
换成"直线方向 + 跨度 + 首点",这是本题从
跳到多项式复杂度的关键。 - 几何约束代数化:本原方向上的格点是等距等差数列,"距离
"直接变成 “下标差 ”,几何问题降维成组合问题。 - 插空法:
里那一项 就是"把跨度切成 段、 每段 "的标准计数,写题时把变量替换写清楚比死记公式更可靠。 - 模数不是质数就不能用逆元:看到
要立刻想到它 ,组合数必须 递推打表;这类"模数陷阱"在计数题里出现频率很高。 - 精确整数判定:
一律改写成 ,是本题最容易写错的一个细节。
备注
本题素材源(new_ROJ/problems/1812/)带自造数据生成脚本 data.py:10 个测试点由
std.cpp 跑出(含手算校验的退化网格点、顶格点、样例复现点),题面来源标注为
“信息学奥赛一本通 · 高手训练篇 · 六、数学基础”。本仓库 main.cpp / main.py 是按题面
独立实现后与这 10 组数据逐点比对的,10/10 一致;题面与官方原题的表述可能有细微偏差,
以题面给出的 6 组样例为准。

