hdu 4790 Just Random

发布时间:2014-10-23 23:29:58
来源:分享查询网

题意:给出两个区间[a,b]和[c,d],分别从这两个区间等概率的抽两个整数x,y,求(x+y)%p=m的概率。 思路:总的组合数很容易算出来,也就是两个区间的整数的个数的乘积。接下来是求两个数的和,对于一个区间,我们可以根据区间模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的情况             0      1       2         3         4         5          6          7             3      2       1         0         7         6          5          4           这样一个完整的区间中两个数的和对p取模等于m的对应关系就确定了。接下来就是分区间讨论,对于完整的区间可以完全对应,因此是p,对于不完整的区间,算出它对应的区间,然后跟另一个区间比较,看覆盖的长度就行了。这题想到这应该就没问题了,但是写起来还是挺容易错的。   代码:   #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<vector> #include<queue> using namespace std; typedef long long ll; struct Node { ll prel,prer; ll sufl,sufr; ll z; }; Node getNode(ll a,ll b,ll p) { Node node; node.prel=a%p; node.z=0; ll pos=a+(p-node.prel-1); if(pos>b) { node.prer=b%p; node.sufl=node.sufr=-1; } else if(pos==b) { node.prer=b%p; node.sufl=node.sufr=-1; } else { node.prer=pos%p; if(b-pos<p) { node.sufl=(pos+1)%p; node.sufr=(b-pos)%p-1; node.z=0; } else { node.z=(b-pos)/p; ll tmp=(b-pos)%p; if(tmp==0) { node.sufl=node.sufr=-1; } else { node.sufl=0; node.sufr=(b-pos)%p-1; } } } return node; } ll getLen(ll a,ll b,ll c,ll d) { if(a>d||b<c) return 0; if(a<c&&b>d) return d-c+1; if(b>=c&&b<=d) return b-max(a,c)+1; return min(b,d)-a+1; } ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int main() { //freopen("in.txt","r",stdin); int t,tcase=0; ll a,b,c,d,m,p; scanf("%d",&t); while(t--) { tcase++; scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&d); scanf("%I64d%I64d",&p,&m); Node x,y; x=getNode(a,b,p); y=getNode(c,d,p); ll ans=0; ll lx,ly,la=-1,lb=-1; //前前 if(x.prer<=m) lx=m-x.prer,ly=m-x.prel; else if(x.prel>m) lx=p-(x.prer-m),ly=p-(x.prel-m); else lx=0,ly=m-x.prel,la=p-(x.prer-m),lb=p-1; ans+=getLen(y.prel,y.prer,lx,ly); if(la!=-1) ans+=getLen(y.prel,y.prer,la,lb); //前中 ans+=(x.prer-x.prel+1)*y.z; //前后 if(y.sufl!=-1) { ans+=getLen(y.sufl,y.sufr,lx,ly); if(la!=-1) ans+=getLen(y.sufl,y.sufr,la,lb); } //中前 ans+=(y.prer-y.prel+1)*x.z; //中中 ans+=x.z*y.z*p; //中后 if(y.sufl!=-1) ans+=(y.sufr-y.sufl+1)*x.z; //后 if(x.sufl!=-1) { //后前 la=lb=-1; if(x.sufr<=m) lx=m-x.sufr,ly=m-x.sufl; else if(x.sufl>m) lx=p-(x.sufr-m),ly=p-(x.sufl-m); else lx=0,ly=m-x.sufl,la=p-(x.sufr-m),lb=p-1; ans+=getLen(y.prel,y.prer,lx,ly); if(la!=-1) ans+=getLen(y.prel,y.prer,la,lb); //后中 ans+=(x.sufr-x.sufl+1)*y.z; //后后 if(y.sufl!=-1) ans+=getLen(y.sufl,y.sufr,lx,ly); if(y.sufl!=-1&&la!=-1) ans+=getLen(y.sufl,y.sufr,la,lb); } ll fenmu=(b-a+1)*(d-c+1); ll g=gcd(ans,fenmu); fenmu/=g; ans/=g; printf("Case #%d: %I64d/%I64d\n",tcase,ans,fenmu); } return 0; }  

返回顶部
查看电脑版