方格計數

傳送門

題意：

在左下角是 \((0, 0)\)，右上角是 \((W, H)\) 的網格上，有 \((W + 1) × (H + 1)\) 個格點。 現在要在格點上找 N個不同的點，使得這些點在一條直線上。并且在這條直線上，

相鄰點之間的距離不小于 D。求方案數模 \(10^9 + 7\)。

做法：

枚舉矩形（右上角端點 \((x,y)\) ），以其兩條對角線（如果長或寬為 0 則隻有一條）作為所需直線，強制選其兩個端點，中間有 \(gcd(x,y)-1\) 個點。

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=505;
ll c[N][N];
ll mod=1e9+7;
ll n,w,d,h;
int gcd(int x,int y)
{
	if(!y) return x;
	return gcd(y,x%y);
}
double calc(int x,int y)
{
	return sqrt((x*x*1.0+y*y));
}
ll solve(ll x,ll y)
{
	if(!x&&!y) return 0;
	ll g=gcd(x,y);
	int k=(int)(ceil(d/calc(x/g,y/g)));
	if(k*(n-1)>g ) return 0;
	ll ans=c[g-1-2*(k-1)-(k-1)*(n-3)][n-2];
	if(x&&y) ans<<=1,ans%=mod;
	return ans*(w-x+1)%mod*(h-y+1)%mod;
}
signed main()
{
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	for(int i=0;i<=500;i++)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++)
		c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&n,&w,&h,&d);
		if(n==1){
			printf("%lld\n",(w+1)*(h+1));
			continue;
		}
		ll ans=0;
		for(int i=0;i<=w;i++)
		for(int j=0;j<=h;j++)
		ans=(ans+solve(i,j))%mod;
		printf("%lld\n",ans);
	}
 }