Can someone please help me, I got TLE on O(N) on 714B?
mod = 10**9 + 7
for _ in range(int(input())):
n = int(input())
arr = list(map(int,input().split()))
count = arr[0]
f = 1
for i in range(1,n):
count&=arr[i]
f*=i
f//=(n-1)
t = arr.count(count)
p = 1
if(t<=1):
print(0)
else:
p = t*(t-1)
re = p*f
print(re%mod)
I think its the 'f', you calculate f = n!, but for n = 2e5 the value is too big and the time to calculate this in python is too large. As you want the answer modulo M, you can try to calculate the answer modulo M in the for, and use modular inverse for the division.
Thankyou
Calculating
ffor a largenwill be too slow. Instead you can take mod at each step. Replacingf*=ibyif i<n-1: f=(f*i)%modand removing thef//=n-1might work.Thankyou
For large numbers (in this case of size 1e5) even simple operations like multiplication will behave like a linear time operation. In this case, while calculating factorial of do modulo operation after each multiplication to keep the size of the number small. -> f = (f*i)%mod
Thankyou