SRM543 Div1 Easy(250), Div2 Medium(500) EllysXors

TopCoder

EllysXors

ビットごとに1を数える。

long long f(long long X)
{
    long long A = 0;
    for ( int i=0; i<60; i++ )
    {
        long long n = (X>>(i+1))<<i;
        if (X>>i&1)
            n += (X&((1LL<<i)-1)) + 1;
        A |= (n&1)<<i;
    }
    return A;
}

class EllysXors{public:
long long getXor( long long L, long long R )
{
    return f(R)^f(L-1);
}};

long longのままでは遅いけど、unsigned intならナイーブな解法が間に合うらしい。最悪ケースで1.8秒。気付かなかったorz

2012-05-19 - kojingharangの日記 - TopCoder部

class EllysXors{public:
long long getXor( long long L, long long R )
{
    unsigned int l = (unsigned int)L;
    unsigned int r = (unsigned int)R;
    unsigned int ans = 0;
    for ( unsigned int i=l; i<=r; i++ )
        ans ^= i;
    return ans;
}};