题意

在左下角是 $(0,0)$，右上角是 $(W,H)$ 的网格上，有 $(W+1)\times (H+1)$ 个格点。

现在要在格点上找 $N$ 个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。

解析

纯组合方法求方案数，是我不会的东西。所以赛时就考虑用 dp 来统计方案数。

通过 P3166 [CQOI2014]数三角形 的套路，我们可以想到枚举 $(x,y)$，即确定一条线段 $(0,0)-(x,y)$，并强制选择这两点，然后通过乘上 $(W-i+1)\times(H-j+1)\times2$ 来统计所有相同线段的答案以及左右翻转后的答案（水平或垂直的线段不需乘二）。

容易利用 gcd 计算出这条线段中间的点数，再通过一通计算，可以算出每两个被选择的点之间至少需要间隔几个点，问题转化为了共有 $i$ 个点，你需要选择 $j$ 个点，且每个点之间至少要间隔 $k$ 个点的方案数，我们记作 $f_{i,j,k}$。

通过 dp 可以在 $O(NWH)$ 的时间内预处理出所有的 $f_{i,j,k}$。枚举每个 $k$ 进行 dp 即可，注意边界条件。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const double eps=1e-8;
const int N=505;
const int mod=1e9+7;
int f[N][55][N];
inline void solve(int k){
    for(int i=1;i<=500;i++) f[i][0][k]=1,f[i][1][k]=i;
    for(int i=2;i<=500;i++){
        for(int j=2;j<=min(50ll,i);j++){
            if(i-k-1>=1) f[i][j][k]=(f[i-k-1][j-1][k]+f[i-1][j][k])%mod;
            else f[i][j][k]=f[i-1][j][k];
        }
    }
}
inline int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
inline double Dis(int x,int y){
    return sqrt(x*x+y*y);
}
int T,W,H,D,n,ans;
signed main(){
    for(int i=0;i<=500;i++) solve(i);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld%lld",&n,&W,&H,&D);ans=0;
        if(n==1){printf("%lld\n",(W+1)*(H+1)%mod);continue;}
        for(int i=0;i<=W;i++){
            for(int j=0;j<=H;j++){
                if(i==0&&j==0) continue;
                int k=gcd(i,j)-1;
                if(k<n-2) continue;
                double dis=Dis(i,j),jg=dis/(double)(k+1);
                if(dis<D) continue;
                int sp=(double)D/jg;
                if((double)D/jg-sp<=eps) sp--;
                int ret;
                if(k-2*sp<=0){
                    if(n==2) ret=1;
                    else ret=0;
                }
                else ret=f[k-2*sp][n-2][sp];
                if(i==0||j==0) ans=(ans+ret*(W-i+1)%mod*(H-j+1)%mod)%mod;
                else ans=(ans+ret*(W-i+1)%mod*(H-j+1)%mod*2%mod)%mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}