首页 > ACM题库 > HDU-杭电 > HDU 4790-Just Random-概率-[解题报告]HOJ
2015
09-18

HDU 4790-Just Random-概率-[解题报告]HOJ

Just Random

问题描述 :

  Coach Pang and Uncle Yang both love numbers. Every morning they play a game with number together. In each game the following will be done:
  1. Coach Pang randomly choose a integer x in [a, b] with equal probability.
  2. Uncle Yang randomly choose a integer y in [c, d] with equal probability.
  3. If (x + y) mod p = m, they will go out and have a nice day together.
  4. Otherwise, they will do homework that day.
  For given a, b, c, d, p and m, Coach Pang wants to know the probability that they will go out.

输入:

  The first line of the input contains an integer T denoting the number of test cases.
  For each test case, there is one line containing six integers a, b, c, d, p and m(0 <= a <= b <= 109, 0 <=c <= d <= 109, 0 <= m < p <= 109).

输出:

  The first line of the input contains an integer T denoting the number of test cases.
  For each test case, there is one line containing six integers a, b, c, d, p and m(0 <= a <= b <= 109, 0 <=c <= d <= 109, 0 <= m < p <= 109).

样例输入:

4
0 5 0 5 3 0
0 999999 0 999999 1000000 0
0 3 0 3 8 7
3 3 4 4 7 0

样例输出:

Case #1: 1/3
Case #2: 1/1000000
Case #3: 0/1
Case #4: 1/1

题意:求从[a,b],[c,d]两个区间找到两个数使得他们的和%p=m,求概率

思路:我们想办法把区间的左范围化到0,那么结果就相对好弄了,应用容斥原理比直接解答问题简单点,假设f(a,b)是区间[0,a],[0,b]中满足条件的个数,设p=6.m=2

那么第一个区间可以看成 : A=[0,1,2,3,4,5]+[0,1,2,3,4,5]+….. B= (0,1,2,3,4)

       第二个区间可以看成:C=[0,1,2,3,4,5]+….D=(0,1)

那么题目就可以看成:A+C,A+D, B+D ,C+D的结果和

前三个不难算,关键是第四个:根据与m的大小做对比,假设B最大的是ma,D最大的是mb

那么当ma>m的时候,我们可以尝试从mb的范围里找是否有能与ma中小于m的数中结合成m,还有的情况是从mb中找一个使得他们和大于p且%p=m;另一种情况就相对简单点了,具体的还有差别,动手模拟一下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

ll a,b,c,d,p,m;

ll gcd(ll a, ll b){
	if (b == 0)	
		return a;
	return gcd(b,a%b);
}

ll f(ll a, ll b){
	if (a < 0 || b < 0)
		return 0;
	ll ma = a%p, mb = b%p;
	ll ans = (a/p)*(b/p)*p;
	ans += (ma+1)*(b/p) + (mb+1)*(a/p);
	if (ma > m){
		ans += min(m, mb) + 1;
		ll t = (p+m-ma) % p;
		if (t <= mb)
			ans +=  mb-t+1;
	}
	else {
		ll t = (p+m-ma)%p;
		if (t <= mb)
			ans += min(m-t+1, mb-t+1);
	}
	return ans;
}

int main(){
	int cas = 1,t;
	scanf("%d", &t);
	while (t--){
		scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &p, &m);
		ll ans = f(b, d)-f(b, c-1)-f(a-1, d)+f(a-1, c-1);
		ll tot = (b-a+1)*(d-c+1);
		ll g = gcd(ans, tot);
		printf("Case #%d: ", cas++);
		cout << ans/g << "/" << tot/g << endl;
	}
	return 0;
}

参考:http://blog.csdn.net/u011345136/article/details/25457981