UVa 12024 – Hats


#include <iostream>
using namespace std;

//int  factorial[14] ;
int wrong[14];
int m;

int C(int n, int r){
	return factorial[n]/factorial[n-r]/factorial[r];
}

int solve (int n){
	if (wrong[n] != -1)return wrong[n];
	else{
		wrong[n] = 0;
		for(int i=1;i<=n;i++){
			wrong[n] += C(n,i)*solve(n-i);
		}
		wrong[n] = factorial[n] - wrong[n];
		return wrong[n];
	}
}

int main(){
	int tc,i;

   //calculating the first 14 factorial;
	factorial[0] = 1;
	for (i = 1 ; i <= 14; i ++){
		factorial[i] = i*factorial[i-1];
		wrong [i]= -1;
	}


	wrong[0]= 1;
	wrong[1]= 0;
	cin>>tc;
	while(tc--){
		cin>>m;
		cout<<solve(m)<<"/"<<factorial[m]<<endl;
	}

   //all possible cases = n! == P(n,n);
   //no one has a right hat = all possible cases - (1 has right hat + 2 have right hats + .... + n have right hats)
   // solve (n) = n! - solve (n-1);
   //it's the power of recursion 😀 😀

	return 0;
}