【HDOJ 5419】Victor and Toys(配列組合せ)

【HDOJ 5419】 Victor and Toys
n個おもちゃm個区間
各おもちゃにはbeauty値が1つあり、3つの区間3区間のMINleft~MAXrightの和の期待値を任意に問う
前処理の1つの配列は、各位置がいくつかの区間で囲まれていることを格納し、このように位置が選択される確率はc(x,3)/c(m,3)である.
beauty配列がwである場合の前処理配列a
期待値はw[i]*c(a[i],3)/c(m,3)i∈[1,n]である.
注意乗算爆発防止long long
コードは次のとおりです.

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long

using namespace std;

int w[50001];
int ad[50002];

ll C(ll n)//c(n,3)
{
    if(n < 3) return 0;
    ll ans = 1;
    for(int i = 2; i >= 0; --i)//  long long
        ans = ans*(n-i)/(3-i);

    return ans;
}

ll gcd(ll a,ll b)//  
{
    ll tmp;
    while(b)
    {
        tmp = b;
        b = a%b;
        a = tmp;
    }
    return a;
}

int main()
{
    int t,n,m,i,l,r;
    ll fz,fm,gd,lst;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        for(i = 1; i <= n; ++i)
            scanf("%d",&w[i]);
        memset(ad,0,sizeof(ad));
        for(i = 0; i < m; ++i)
        {
            scanf("%d %d",&l,&r);
            ad[l]++;
            ad[r+1]--;
        }
        if(m < 3)//       。。    
        {
            puts("0");
            continue;
        }

        fm = C(m);

        fz = lst = 0;
        for(i = 1; i <= n; ++i)//              。。
        {
            lst += ad[i];
            fz += w[i]*C(lst);
        }

        gd = gcd(fz,fm);
        fz /= gd;
        fm /= gd;
        if(fm == 1) printf("%I64d
",fz);
        else printf("%I64d/%I64d
",fz,fm);
    }

    return 0;
}