We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Chandrima and XOR
  5. Discussions

Chandrima and XOR

Sort by

recency

|

8 Discussions

|

  • cafelatte
     + 0 comments

    If you know Zeckendorf representation it's kind of trivial.
    Python3 

    def solve(a):
    fib = [1,2]
    for _ in range(100): fib.append(fib[-2]+fib[-1])
    def zeck(n): # Zeckendorf representation
        if n > fib[-1]: raise ValueError('Out of range')
        ret = ''
        for f in reversed(fib):
            if n >= f:
                ret += '1'
                n -= f
            else:
                ret += '0'
        return ret.lstrip('0')
    ret = 0
    for _ in a: ret ^= int(zeck(_),2)
    return ret % (10**9+7)

  • gradysocool
     + 0 comments

    Hardest part was realizing that my time outs was because their java code for I/O wasn't fast enough, so I had to write my own, smh.

  • ygrinev
     + 0 comments

    The fastest way - not to use power of 2 at all:

    static int solve(IEnumerable<long> a)
{
    ulong[] fib = new ulong[100]; fib[0] = 1; fib[1] = 2;
    int i = 2;
    ulong max = (ulong)a.Max(), nextFib = 3;
    // fill out fibonachi seq
    while (nextFib <= max) { nextFib = fib[i - 1] + fib[i - 2]; fib[i++] = nextFib; }
    // fill out bitwise future result
    var pow2 = a.Aggregate(Enumerable.Repeat(false, i).ToArray(), (xor, next)=> { zen(fib, xor, (ulong)next); return xor; });
    i = pow2.Length;
    ulong ret = 0;
    int idx = 0;
    ulong pow2_60_mod1000000007 = 536_396_504, mod = 1; // = 2^60 mod 1000000007, 2^61%1000000007=(536_396_504*2)%1000000007
    while (i > 0)
    {
        ret = (ret + mod*(Convert.ToUInt64(string.Join("", pow2.Skip((idx++) * 60).Take(60).Reverse().Select(b=>b?"1":"0")), 2)%1000000007)%1000000007)%1000000007;
        mod = (mod * pow2_60_mod1000000007) % 1000000007;
        i -= 60;
    }
    return (int)ret; // pow2.Aggregate((ulong)0, (ret, next)=>(ret + poq2mod(pow2[i], ref i))%1000000007);
}
private static void zen(ulong[] fibs, bool[] pow2, ulong next)
{
    if (next < 1) return;
    int idx = fibs.TakeWhile(n => n <= next && n > 0).Count();
    do
    {
        if(fibs[--idx] <= next)
        {
            pow2[idx] = !pow2[idx];
            next -= fibs[idx];
        }
    }
    while (next > 0);
}

    Then you have just an array of bits for idx of pow 2...

  • appujose100
     + 0 comments

    I was observing some of your content on this site and I found this website is truly educational! Website Designing Services in Dubai

  • TChalla
     + 1 comment

    Python3 code

    # The XOR is simple enough. The trick is that they haven't given us the
# numbers to XOR, but their position in the list. To find the actual
# numbers, determine the number of numbers up to N bits long in the list.
# Count 0, since we can add any new bit to zero.
# Then there are 2 numbers with up to 1 bit, 3 with up to 2 bits, etc.
# To add the numbers with N bits, add the number of numbers with N-2 bits
# or less to the previous total (the numbers for N-1 bits).
# The result is the fibonacci sequence, since I just keep adding the last
# two numbers. And so the number I want is the Zeckendorf representation
# of the given index, reinterpreted as binary (repeatedly subtracting the
# largest Fibonacci number available from the index)
#
# I've got one case here that is failing, probably just barely failing the time limit.
# Let's try precalculating the powers as the small speedup needed.

def zeck(n):
    res = 0
    for i in range(f - 1, -1, -1):
        if n >= fib[i]:
            n -= fib[i]
            res += p2[i]
    return res

n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
    fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
    p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
    sol = sol ^ zeck(nums[j])
print(sol % modulus)