[UVA] 12024 - Hats

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12024 - Hats
Source            : UVA Online Judge
Category          : Combinatorics
Algorithm         : Derangement
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll              long long  
6.   
7. static const int maxn = 21;  
8.   
9. ll nCr[maxn][maxn];  
10. ll fact[maxn];  
11.   
12. void factorial()  
13. {  
14.       fact[0] = 1;  
15.       for (int i = 1; i <= 20; i++) fact[i] = i * fact[i-1];  
16. }  
17.   
18. void combination()  
19. {  
20.       nCr[0][0] = 1;  
21.       for (int i = 1; i <= 20; i++)  
22.       {  
23.             nCr[i][i] = 1;  
24.             nCr[i][0] = 1;  
25.             for (int j = 1; j < i; j++)  
26.             {  
27.                   nCr[i][j] = nCr[i-1][j] + nCr[i-1][j-1];  
28.             }  
29.       }  
30. }  
31.   
32. int main()  
33. {  
34.       factorial();  
35.       combination();  
36.   
37.       int tc;  
38.       scanf("%d", &tc);  
39.       for (int tcase = 1; tcase <= tc; tcase++)  
40.       {  
41.             int n;  
42.             scanf("%d", &n);  
43.             ll derangement = fact[n];  
44.             for (int i = 1; i <= n; i++)  
45.             {  
46.                   if (i & 1) derangement -= nCr[n][i] * fact[n-i];  
47.                   else derangement += nCr[n][i] * fact[n-i];  
48.             }  
49.             printf("%lld/%lld\n", derangement, fact[n]);  
50.       }  
51. }