#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; }

Advertisements