方格計數

• description
• solution
• code

description

在左下角是 (𝟎, 𝟎)，右上角是 (W, H)的網格上，有 (W + 1) × (H + 1) 個格點。
現在要在格點上找 N個不同的點，使得這些點在一條直線上。并且在這條直線上，
相鄰點之間的距離不小于𝐃。求方案數模 10⁹ + 7

【輸入格式】
第一行一個整數 𝐓，表示數據組數。
接下來 𝐓 行，每行四個整數 N, W, H, D，意義如題目描述。

【輸出格式】
𝐓 行，每行一個整數表示答案。

【樣例 1 輸入】

7 2 2 3 3 1 4 5 3 1 251 497 2 5 40 28 10 2 2 2 2 18 60 58 2 19 2 58 4

【樣例 1 輸出】

9 30 125496 597 16 172006701 0

【數據范圍】

對于 100% 的數據， 1 ≤ N ≤ 50， 1 ≤ W, H, D ≤ 500， 1 ≤ T ≤ 20

solution

在一個以$(0,0)$開始的二維網格中，一條線段$(0,0)?(x,y)$含有整數點的個數為$\gcd (x,y)?1$（不包含線段的兩個整數端點）

有$n$個盒子，從中選$m$個，且相鄰兩個盒子之間至少有$k$個盒子的組合方案為$\left(\genfrac{}{}{0ex}{}{n?k(m?1)}{m}\right)$

證明：$m$個盒子會造成$m?1$個長度至少為$k$的盒子空隙，減去這$(m?1)k$個盒子，剩下的就相當于是隨便選位置了

---

首先，暴力的想法，枚舉兩個端點，橫坐標之差的絕對值為$x$，縱坐標之差的絕對值為$y$，那么這里面包含的整數點個數為$g?1,g=\gcd (x,y)$

強制兩個端點必須選，那么剩下還要選$n?2$個

求出相鄰兩個盒子之間編號差至少為$k$（利用兩點間距離公式和題目要求的$d$），即兩個盒子之間的盒子個數至少為$k?1$

兩個端點選了會導致兩個$k?1$的長度區間盒子不能選

剩下的盒子數只有$g?1?2(k?1)$

套用上面的組合數公式，即$\left(\genfrac{}{}{0ex}{}{g?1?2(k?1)?(n?3)(k?1)}{n?2}\right)$

不難發現，最后只與橫縱坐標差有關，所以直接枚舉橫縱坐標差，乘以情況數$(w?x+1)(h?y+1)$即可

但是這個差是絕對值差，所以如果不是水平或豎直線，就有兩種情況（可以理解為$y$有正負，一條指向左方的線對稱有指向右方的線；也可以理解為$x$有正負，一條指向下方的線對稱有一條指向上方的線）

code

#include <cstdio> #include <cmath> using namespace std; #define maxn 505 #define int long long #define mod 1000000007 int T, n, w, h, d; int c[maxn][maxn];void init() {for( int i = 0;i < maxn;i ++ ) {c[i][0] = c[i][i] = 1;for( int j = 1;j < i;j ++ )c[i][j] = ( c[i - 1][j] + c[i - 1][j - 1] ) % mod;} }int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y ); }double calc( int x, int y ) {return sqrt( x * x * 1.0 + y * y ); }int solve( int x, int y ) {if( ! x and ! y ) return 0;int g = gcd( x, y );int k = ( int )ceil( d / calc( x / g, y / g ) );if( k * ( n - 1 ) > g ) return 0;int ans = c[g - 1 - 2 * ( k - 1 ) - ( k - 1 ) * ( n - 3 )][n - 2];if( x and y ) ans = ( ans << 1 ) % mod;return ans * ( w - x + 1 ) % mod * ( h - y + 1 ) % mod; }signed main() {init();scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld %lld %lld", &n, &w, &h, &d );if( n == 1 ) {printf( "%lld\n", ( w + 1 ) * ( h + 1 ) );continue;}int 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 );}return 0; }

總結

以上是生活随笔為你收集整理的2021牛客NOIP提高组第二场T2——方格计数（组合数计数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。