[UVa] 12024 - Hats

A good explaination on this problem can be found here [ https://gist.github.com/Tafhim/b5705901e33017205a3b ]
I used the formula for the DP implementation

D(n) = n D(n-1) + (-1)^n

Solution:

#include <bits/stdc++.h>
using namespace std;

map<int, pair<int, int> > precalc;
int main() {
 int kase, n, ai;
 int de[100], f[100];
 de[0] = 1;
 f[0] = 1;
 de[1] = 0;
 f[1] = 1;
 ai = -1;
 for (int i = 2 ; i<=12 ; i++) {
  ai *= (-1);
  de[i] = i * de[i-1] + ai;
  f[i] = f[i-1]*i;
 }

 cin >> kase;

 while (kase--) {
  cin >> n;
  cout << de[n] << "/" << f[n] << endl;
 }

 return 0;
}