http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4352

问题化为计算[1,n]的红气球个数。
结合n=6和n=5的计算方法,可得到如下公式。

/*0.016s*/
const int mx = 31;

ll num[mx] = {1LL};

ll f(int n, int k)
{
    ll ans = 0LL;
    int i;
    rFor(i, mx - 1) if (n & (1 << i))
    {
        ans += num[i] * (1 << (k - i)); /// 对比题目的图,你算算n=6和n=5的情况就知道这个公式是怎么来的了
        --k, n -= 1 << i;
    }
    return ans;
}

int main()
{
    int t, cas = 0, k, a, b, i;
    Forr(i, 1, mx) num[i] = 3 * num[i - 1];
    SI(t);
    while (t--)
    {
        Pcas();
        SIII(k, a, b);
        PL(f(b, k) - f(a - 1, k));
    }
    return 0;
}

Comments

comments powered by Disqus