Gym 100425A Luggage Distribution (组合数学，二分)

一开始想着球盒模型，数据范围大，递推会GG。

用凑的方法来算方案。往n个小球之间插两个隔板，方案是(n-1)*(n-2)/2，不区分盒子，三个盒子小球数各不相同的方案数被算了6次(做排列)，

两个相同的被算了3次，如果n可以被3整除，那么3个相同的被算了一次。全部都加到6，在一起除以6就得到总的方案数。

方案数对n的函数具有单调性，因此二分答案。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll cal(ll n)

{

    return ((n-)*(n-)/+(n-)/*+!(n%)*)/;

}

ll chaos(ll x)

{

    ll L = , R = 2e9,mid;

    for(;L<R; cal(mid)<x?L=mid+:R=mid ) mid = (L+R)>>;

    return L;

}

int main()

{

    ll L,R;

    scanf("%I64d%I64d",&L,&R);

    ll sL = chaos(L), sR = chaos(R+);//由于二分本身是找下界所以写成R+1变成找上界

    printf("%I64d",sR-sL);

}

巴特西

Gym 100425A Luggage Distribution (组合数学，二分)

最新文章

热门文章