Soluție HackerRank pentru Number of zero-xor subsets, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și…

  • Problemă: Number of zero-xor subsets
  • Domeniu: Number Theory
  • Limbaj: Python 3

Challenge: Number of zero-xor subsets

Subdomeniu: Number Theory (number-theory)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464739172

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/number-of-subsets/problem

Cerință

You are given an integer N. Consider set S = {0, 1,… , 2 ^ N - 1}. How many subsets Asubset S with bigoplus_x in Ax = 0 (oplus denotes xor operation) are there?
Print your answer modulo (10^9 + 7).
Note that the xorsum of an empty set is zero!

Input Format
The first line contains one integer T, the number of testcases.
The next T lines contain one integer N each.

Output Format
Output T lines. Each line is one number, answer to the problem modulo 10^9 + 7.

Constraints
1 ≤ T ≤ 10000
1 ≤ N ≤ 10 ^ {18}

Sample Input

2
1
2

Sample Output

2
4

Explanation
For N = 1 there are 2 sets - varnothing and {0}.
For N = 2 there are 4 sets - varnothing, {0}, {1, 2, 3}, {0, 1, 2, 3}.

Cod sursă

import sys

MOD = 1000000007
PHI = MOD - 1

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    out = []
    for i in range(1, t + 1):
        n = int(data[i])
        e = (pow(2, n, PHI) - (n % PHI)) % PHI
        out.append(str(pow(2, e, MOD)))
    sys.stdout.write('\n'.join(out))

if __name__ == '__main__':
    main()
HackerRank Number Theory – Number of zero-xor subsets