时间戳

首页 > 解决方案 > Xor Equality（codechef may 21 挑战）对于某些值，例如 n=4589，我得到了错误的结果，感谢您的帮助:)

c++ - Xor Equality（codechef may 21 挑战）对于某些值，例如 n=4589，我得到了错误的结果，感谢您的帮助:)

问题描述

/*对于给定的 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;
}

标签： c++xormodulo

解决方案

在实践中，解决方案只是 2 的幂：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;
}

推荐阅读