link : Contest Page | CodeChef someone please give algo or solve in C++
This is a PNC (principle of inclusion and exclusion) based problem, In this you have to firstly find the no of combination of choosing 3 person among the n person, then by using principle of inclusion and exclusion find the total possible combination for each person not having their own cap.
My code in PYTHON :
fact=*(50) for i in range(1,41): fact[i]=fact[i-1]*i n=int(input()) ans=0 tot=n*(n-1)*(n-2)//6 n-=3 for i in range(n+1): if i%2==0: ans+=(fact[n]//(fact[n-i]*fact[i]))*fact[n-i] else: ans-=(fact[n]//(fact[n-i]*fact[i]))*fact[n-i] ans*=tot print(ans)
You can use similar approch in c++ but using long long can lead to overflow so you can use a 128 bit int but not sure it will work as upper limit of n is not given so in value more than 34 it will overflow that too.