思路与算法

枚举本原整数方向(x,y)，gcd=1，横竖单列，两种斜率对称乘2。一条最大格点线含L点，所选相邻点的索引差至少g，其中g是满足g²(x²+y²)≥D²的最小正整数。在线上选N点方案为C(L-(g-1)(N-1),N)。S(k)=(W-(k-1)x+1)+(H-(k-1)y+1)+计k点连续段；最大线恰长L的数量为S(L)-2S(L+1)+S(L+2)，据此累加。

正确性说明

任意至少2个共线点唯一决定本原方向及所在最大线。间距约束等价排序索引间隔至少g，移去各前缀额外空隙后得到无约束组合选取。长度L的最大线含max(L-k+1,0)个k段，二阶差分恰好提取指定L线数，因此每个点集仅计一次。

复杂度

Pascal表初始化O(500·50)。每组方向枚举O(WH)，各方向长度循环总复杂度可写O(Σ方向 min(W/x,H/y))，粗上界O(WH·min(W,H))，实际由调和求和显著更小；另有求g的O(D)粗界。空间O(500·50)。所有20组满规模用例按原1秒限制执行。

易错点

模数1e9为合数，组合数用加法递推，不能用费马逆元。判断距离使用整数平方，避免开方边界。N=1时所有格点各是一种方案，单列；原网格有(W+1)(H+1)点。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 1000000000;
ll C[503][51];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i <= 502; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= 50 && j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
    }
    int T;
    cin >> T;
    while (T--) {
        int N, W, H, D;
        cin >> N >> W >> H >> D;
        if (N == 1) {
            cout << (W + 1LL) * (H + 1) % P << '\n';
            continue;
        }
        ll ans = 0;
        auto process = [&](int x, int y, int mult) {
            int L = min(x ? W / x : 1000000, y ? H / y : 1000000) + 1;
            if (L < N)
                return;
            int step = 1;
            while (1LL * step * step * (x * x + y * y) < 1LL * D * D)
                step++;
            auto cnt = [&](int k) -> ll {
                return max(0, W - (k - 1) * x + 1) * 1LL * max(0, H - (k - 1) * y + 1);
            };
            for (int k = N; k <= L; k++) {
                int z = k - (step - 1) * (N - 1);
                if (z < N)
                    continue;
                ll exact = cnt(k) - 2 * cnt(k + 1) + cnt(k + 2);
                ans = (ans + exact % P * C[z][N] % P * mult) % P;
            }
        };
        process(1, 0, 1);
        process(0, 1, 1);
        for (int x = 1; x <= W / (N - 1); x++)
            for (int y = 1; y <= H / (N - 1); y++)
                if (__gcd(x, y) == 1)
                    process(x, y, 2);
        cout << ans << '\n';
    }
}