HDU-4790 Just Random (数形结合)

朱雀 2022-06-09 08:29 117阅读 0赞

![Center][]

![Center 1][]

**题意**：给你a,b,c,d,p,m，随机等可能性的选择一对x，y，x∈\[a,b\]，y∈\[c,d\]，如果(x+y)%p=m，则称这次选择是成功的，问选择的成功率是多少。

**思路**：这道题有一种很好的理解方式，就是数形结合。我们可以把题目中的第一组数据理解为下面这幅图。

![Center 2][]

第一组数据里a=0，b=5，那么x的取值范围就是\[0,5\]，c=0，d=5，那么y的取值范围也是\[0,5\]，那么图中正方形内的所有点，包括边缘上的点，就是全部可能被选到的情况。并且每个点被选到的可能性相同。接下来我们再看p=3，m=0，那么(x+y)%p=m→→x+y=k\*p+m→→x+y=3k，k为任意非负整数。所以图中的红线从左到右依次就对应k为0,1,2,3,4的情况。那么这些红线所经过的点就是满足x+y=3k的点。

所以最终答案就是：正方形中红线经过的点的个数/正方形中全部点的个数

所以第一组数据的答案就是12/36→→1/3

那么接下来问题就转换成了如何才能快速求取红线经过的点的个数，我曾试过枚举每一个k，数据太大，果断T了，仔细观察后发现，可以分三种情况讨论，如下图。

![Center 3][]

首先我们要知道有一点，ab与cd互换对结果是没有任何影响的，因为图中每一条红线都关于y=x对称，将ab与cd互换后的图形也是关于y=x对称的，如图中的蓝色矩形和褐色矩形，所以我们可以假设(b-a)>(d-c)。

那么接下来就会有三种情况：

**1**，红线在①和②之间。因为每相邻两条红线之间相隔的距离是相等的，所以我们不难发现，在①和②之间的红线所经过的点呈等差数列，所以我们只需要找到最小的k1使得k1\*p+m>=a+c(保证红线在红线①的右边或与①重合)，和一个最大的k2使得k2\*p+m<=a+d(保证红线在红线②的左边或与②重合)，那么对于任意的k，k∈\[k1,k2\]，都是满足这一种情况的k，之后利用等差数列求和的公式，可以得出：

红线所经过的点为 ((k1\*p + m - a - c + 1) + (k2\*p + m - a - c + 1))\*(k2 - k1 + 1) / 2;

**2**，红线在②和③之间。同理，我们要找一个最小的k1和一个最大的k2使得对于任意的k，k∈\[k1,k2\]，都是满足这一种情况的k，那么显而易见，k1就等于第一种情况的k2+1。那么k2就是要满足k2\*p+m<=b+c。在这一段区间内的红线，每一条红线经过的点都是相同的，都是(d-c+1)。

红线所经过的点为 (k2-k1+1)\*(d - c + 1);

**3**，红线在③和④之间。同理，k1=第二种情况的k2+1，k2满足k2\*p+m<=b+d。这一段区间内的红线经过的点和第一种情况一样，呈等差数列。

红线所经过的点为((b + d - k1\*p - m + 1) + (b + d - k2\*p - m + 1))\*(k2 - k1 + 1) / 2;

把这三种情况红线经过的点全部加起来，就是答案的分子，答案的分母就是矩形中的全部点(d - c + 1)\*(b - a + 1);

然后用GCD约分一下就是最终答案了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 305;
    const int MOD = 30021;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    LL gcd(LL a, LL b){return b == 0 ? a : gcd(b, a%b);}
    
    int main()
    {
    	int T;
    	LL a, b, c, d, p, m,t,g;
    	LL k1, k2;
    	LL ans;
    	LL aans;
    	scanf("%d", &T);
    	for (int CAS = 1; CAS <= T; CAS++)
    	{
    		ans = 0;
    		scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &p, &m);
    		if ((d - c) > (b - a))
    		{
    			swap(a, c);
    			swap(b, d);
    		}
    		if (a+c - m - 1 < 0)//第一种情况
    			k1 = (a+c - m - 1) / p;
    		else
    			k1 = (a+c - m - 1) / p + 1;
    		if (a + d - m < 0)
    			k2 = (a + d - m) / p - 1;
    		else
    			k2 = (a + d - m) / p;
    		ans += ((k1*p + m - a - c + 1) + (k2*p + m - a - c + 1))*(k2 - k1 + 1) / 2;
    
    		k1 = k2 + 1;//第二种情况
    		if (b + c - m < 0)
    			k2 = (b + c - m) / p - 1;
    		else
    			k2 = (b + c - m) / p;
    		ans += (k2-k1+1)*(d - c + 1);
    
    		k1 = k2 + 1;//第三种情况
    		if (b+d - m < 0)
    			k2 = (b+d - m) / p - 1;
    		else
    			k2 = (b+d - m) / p;
    		ans += ((b + d - k1*p - m + 1) + (b + d - k2*p - m + 1))*(k2 - k1 + 1) / 2;
    
    		aans = (d - c + 1)*(b - a + 1);//总共的点
    		g = gcd(ans, aans);//化简
    		aans /= g;
    		ans /= g;
    		printf("Case #%d: %lld/%lld\n", CAS, ans, aans);
    	}
    }

[Center]: /images/20220609/bbf7fc31e8664bdfa8f45488b861d8af.png
[Center 1]: /images/20220609/3cbf3002b5c64286bef6fbcc7848eb86.png
[Center 2]: /images/20220609/012a3b3c3bb84dab9756ebf99d37ebdd.png
[Center 3]: /images/20220609/fa8e15d130b44220be25b6ec03304599.png