2015年2月12日 星期四

Codechef February Challenge 2015 Xor Matrix

#include <iostream>
#include <cstdio>

using namespace std;

#define MOD (int)(1e9+7)

typedef long long ll;

int T;

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        ll L, R;
        scanf("%lld %lld", &L, &R);

        int i;

        for(i = 1; ; i++)
        {
            ll p = (1LL<<i);

            ll d1 = (0-L%p)%p;
            if( d1 < 0 ) d1 += p;

            ll d2 = ((p-1)-R%p )%p;
            if( d2 > 0 ) d2 -= p;

            if( R-(L+d1) >= p/2 );
            else if( (R+d2)-L >= p/2 );
            else{  break; }
        }

        i--;

        if( i == 0) { printf("0 %lld\n", (R-L+1)%MOD); continue; }

        ll p = (1LL<<i);

        ll d1 = (0-L%p)%p;
        if( d1 < 0 ) d1 += p;

        ll d2 = ((p-1)-R%p )%p;
        if( d2 > 0 ) d2 -= p;

        ll t = p%MOD;
        ll t2 = p/2%MOD;

        ll cnt = 0;
        if( R-(L+d1) >= p/2 )
        {
            ll d = R-(L+d1)+1;
            cnt += d/p%MOD*t%MOD*t2%MOD;
            cnt %= MOD;
            d %= p;
            if( d >= p/2 )
            {
                cnt += (d-p/2)%MOD*2*t2%MOD;
                cnt %= MOD;
            }
        }

        if( (R+d2)-L >= p/2 )
        {
            ll d = (R+d2)-L+1;
            cnt += d/p%MOD*t%MOD*t2%MOD;
            cnt %= MOD;
            d %= p;
            if( d >= p/2 )
            {
                cnt += (d-p/2)%MOD*2*t2%MOD;
                cnt %= MOD;
            }
        }

        printf("%lld %lld\n", (p-1), cnt);

    }
}

沒有留言:

張貼留言