hdoj 4790 Just Random 【数学】

本是古典何须时尚 2022-08-13 10:28 149阅读 0赞

题目：[hdoj 4790 Just Random][]

题意：给你两个闭区间【a,b】,【c，d】，分别从中等可能的跳出 x 和 y ，求（x+y）%p == m的概率

分析：

假如是【3,5】 【4,7】 p = 2 ， m = 1；

则所有的和

78 910

891011

9101112

12 3321

后面一行出现次数，可以发现可以分成三部分，第一部分递增的等差数列，第二部分值都相等，第三部分等差数列

然后用等差数列求和公式求和就ok

AC代码：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #define MAXN 100005
    using namespace std;
    typedef long long LL;
    LL p,m;
    LL gcd(LL a,LL b)
    {
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        for(int cas = 1; cas<=T; cas++)
        {
            LL a,b,c,d,ans = 0;
            scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&p,&m);
            if((b-a)>(d-c))
                swap(a,c),swap(b,d);
            long long t1 = (a+c)%p;
            long long add = (m - t1 + p)%p;
            long long cnt1 = (a+c + add-m)/p;
            long long t2 = (b+c-1)%p;
            long long sub = (t2 - m + p)%p;
            long long cnt2 = (b+c-1-sub-m)/p;
            //cout<<t2<<" "<<sub<<endl;
            ans += (cnt2 - cnt1 + 1)*(1+add) + (cnt2 - cnt1 + 1)*(cnt2 - cnt1)/2 * p;
            t1 = (b+c)%p;
            add = (m - t1 + p)%p;
            cnt1 = (b+c+add-m)/p;
            t2 = (a+d)%p;
            sub = (t2 - m + p)%p;
            cnt2 = (a+d-sub-m)/p;
            ans += (cnt2 - cnt1 + 1)*(b-a+1);
            t1 = (a+d+1)%p;
            add = (m - t1 + p)%p;
            cnt1 = (a+d+1+add-m)/p;
            t2 = (b+d)%p;
            sub = (t2 - m + p)%p;
            cnt2 = (b+d-sub-m)/p;
            ans += (cnt2 - cnt1 + 1)*(1+sub) + (cnt2 - cnt1 + 1)*(cnt2 - cnt1)/2*p;
            long long tot = (b-a+1)*(d-c+1);
            long long GCD = gcd(ans,tot);
            ans /= GCD;
            tot /= GCD;
            printf("Case #%d: %I64d/%I64d\n",cas,ans,tot);
        }
        return 0;
    }

[hdoj 4790 Just Random]: http://acm.hdu.edu.cn/showproblem.php?pid=4790