题意

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

现在要在格点上找 $N$ 个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于 $D$ 。求方案数模 $1 0^{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 (N W H)$ 的时间内预处理出所有的 $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;
}

题解 | #方格计数#

题意

解析

代码