Xor Equality（codechef 5 月 21 日挑战）我得到了一些值的错误结果，比如 n=4589 任何帮助表示赞赏:)

Question

/*对于给定的 N，找出从范围 [0,2N−1] 中选择整数 x 的方法的数量，使得 x⊕(x+1)=(x+2)⊕(x +3), 其中⊕表示按位异或运算符。

由于有效x的个数可以很大，所以对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;
}

Answer 1

实际上，解决方案只是二的幂：answer = 2^{n-1}。

为了提高效率，这意味着最好先迭代计算所有解：

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;
}

Xor Equality（codechef 5 月 21 日挑战）我得到了一些值的错误结果，比如 n=4589 任何帮助表示赞赏:)

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

c++

xor

modulo