Search code examples
c++xormodulo

Xor Equality (codechef may 21 challenge )I am getting wrong results for some values like n=4589 any help is appreciated :)


/*For a given N, find the number of ways to choose an integer x from the range [0,2N−1] such that x⊕(x+1)=(x+2)⊕(x+3), where ⊕ denotes the bitwise XOR operator.

Since the number of valid x can be large, output it modulo 109+7.*/

#include <iostream>

using namespace std;
#define ll long long

const ll N = 1e5;      //user can input n upto 1e5
unsigned ll  arr[N];
unsigned ll p = 1e9 + 7;  // we have to find answer modulo p

ll mod_pow(ll a, ll b)
{
    if (b == 1)
    {
        return a;
    }
    ll   c   =   1;
    if  ( b % 2 == 0)
      c= ( mod_pow ( a  , b / 2) ) % p ; 
    else
    {
        c = ( mod_pow(a, (b - 1) / 2)) % p;
        return ((a % p) * c * c) % p;
    }
    return (c * c)%p;
}


 void pre()
{
    for ( unsigned ll i = 0;i < N;i++)
    {
        arr[i] = ( ( ( ( mod_pow ( 2, i+1) -1 + p ) %p ) * 1/2 ) %p + 1 ) %p;  
                                                  
                       / / precomputing for all even number in (2^n -1) 
    }

}
int main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);
    pre();
    int t;
    cin >> t;

while (t--)
{
    int n;
    cin >> n;
    cout << (arr[n-1])<<endl ;
}

return 0;
}

Solution

  • In practice, the solution is simply a power of two: answer = 2^{n-1}.

    For efficiency, this implies that it is better to first calculate all solutions iteratively:

    powerof2[n] = (2 * powerof2[n-1]) % p
    
    #include <iostream>
    
    constexpr int N = 1e5;      //user can input n up to 1e5
    unsigned long long  arr[N];
    constexpr unsigned int p = 1e9 + 7;  // we have to find answer modulo p
    
    //  pre-compute the powers of 2
     void pre() {
        arr[0] = 1;
        for (int i = 1; i < N; i++) {
            arr[i] = (2 * arr[i-1]) % p;  
        }
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        pre();
        int t;
        std::cin >> t;
    
        while (t--) {
            int n;
            std::cin >> n;
            std::cout << arr[n-1] << std::endl ;
        }
        return 0;
    }