首页 > 其他 > 详细

hdu 4790 Just Random 神奇的容斥原理

时间:2014-05-13 21:49:59      阅读:419      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
 1 /**
 2 大意: 给定[a,b],[c,d]  在这两个区间内分别取一个x,y  使得 (x+y)%p = m 
 3 思路:res = f(b,d) -f(b,c-1)-f(a-1,d)+f(a-1,c-1);   f(b,d ) 表示在[0,b],[0,d] 之间有多少个符合上述要求的数    
 4           1、将[0,b] 分为两部分, b/p  和 b%p  能整除p的[0,(b/p)*p] 和[(b/p)*p+1,b ]  同理[0,d]也可以这样分, 这样对于[0,b]  [0,d ] 分别有两种情况,则一共有四种情况。
 5 a、 对于能整除的部分,直接相乘可得结果ans += (b/p)*(d/p)*p;
 6 b、 对于b 不能整除的和 d 能整除的。。 ans += (b%p+1)*(d/p)
 7 c、 对于d不能整除的和b能整除的。   ans += (d%p+1)*(b/p)
 8 d 、 对于 b不能整除和d也不能整除的。。
 9 先举下面一个例子
10 
11 对于一个完整的区间来说,不难想到[0,m]对应[m,0],那么对于[m+1,p-1]对应哪一个区间呢,一个数a来说,如果a%p=m,则a=m,m+p,m+2*p……由于[0,p-1]中任意两个数的和都小于2*p,因此a只能为m或者m+p,那么[m+1,p-1]就对应着[p-1,m-1]。下面是m=3,p=8的情况
12             0      1       2         3         4         5          6          7
13             3      2       1         0         7         6          5          4          
14 
15 那么。。ma = b%p  mb = d%p。。。
16 若是ma〉m  那么:
17         ans += min(m+1,mb+1);
18         tmp = (p+m-ma)%p;
19         if(tmp<=mb) ans += (mb-tmp+1);
20 
21 若是ma〈 m 那么:
22         tmp = (m-ma+p)%p;
23         if(tmp<=mb)
24             ans += min(m-tmp+1,mb-tmp+1);
25 **/
26 ////////////////////////////////////////////////
27 别人的解释。。。
28 总的组合数很容易算出来,也就是两个区间的整数的个数的乘积。接下来是求两个数的和,对于一个区间,我们可以根据区间模p的结果进行划分:[a%p,p-1],[0,p-1],[0,b%p],也就是说把区间中前面和后面不完整的[0,p-1]的区间单独拿出来分析,中间的完整的一起算就好了。接下来是区间中模p等于m的数的个数,对于一个完整的区间来说,不难想到[0,m]对应[m,0],那么对于[m+1,p-1]对应哪一个区间呢,一个数a来说,如果a%p=m,则a=m,m+p,m+2*p……由于[0,p-1]中任意两个数的和都小于2*p,因此a只能为m或者m+p,那么[m+1,p-1]就对应着[p-1,m-1]。下面是m=3,p=8的情况
29             0      1       2         3         4         5          6          7
30             3      2       1         0         7         6          5          4          
31 这样一个完整的区间中两个数的和对p取模等于m的对应关系就确定了。接下来就是分区间讨论,对于完整的区间可以完全对应,因此是p,对于不完整的区间,算出它对应的区间,然后跟另一个区间比较,看覆盖的长度就行了。这题想到这应该就没问题了,但是写起来还是挺容易错的。
32 ////////////////////////////////////////////////
33 
34 #include <iostream>
35 #include <algorithm>
36 using namespace std;
37 long long a,b,c,d,p,m;
38 
39 long long min(long long a,long long b){
40     return a<b?a:b;
41 }
42 
43 long long sol(long long b,long long d){
44     if(b<0||d<0)
45         return 0;
46     long long ma,mb;
47     long long ans =0;
48     long long tmp;
49     ans += (b/p)*(d/p)*p;
50     ma = b%p;
51     mb = d%p;
52     ans += (ma+1)*(d/p) + (mb+1)*(b/p);
53     if(ma>m){
54         ans += min(m+1,mb+1);
55         tmp = (p+m-ma)%p;
56         if(tmp<=mb) ans += (mb-tmp+1);
57     }else{
58         tmp = (m-ma+p)%p;
59         if(tmp<=mb)
60             ans += min(m-tmp+1,mb-tmp+1);
61     }
62     return ans;
63 }
64 
65 long long gcd(long long a,long long b){
66     if(b==0)
67         return a;
68     return gcd(b,a%b);
69 }
70 
71 int main()
72 {
73     int t;
74     cin>>t;
75     int cnt;
76     for(cnt=1;cnt<=t;cnt++){
77         cin>>a>>b>>c>>d>>p>>m;
78         long long res;
79         res = sol(b,d)-sol(b,c-1)-sol(a-1,d)+sol(a-1,c-1);
80         long long sum =(long long ) ((b-a+1)*(d-c+1));
81         long long gcdD = gcd(res ,sum);
82        // cout<<res<<"------------>"<<sum<<endl;
83         res = res/gcdD;
84         sum = sum/gcdD;
85         cout<<"Case #"<<cnt<<": ";
86         cout<<res<<"/"<<sum<<endl;
87     }
88     return 0;
89 }
bubuko.com,布布扣

 

hdu 4790 Just Random 神奇的容斥原理,布布扣,bubuko.com

hdu 4790 Just Random 神奇的容斥原理

原文:http://www.cnblogs.com/Bang-cansee/p/3724060.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!