SRM391 div1 medium

ステージ1:
4番を爆破したとする。すると1番も開けることができる。

このような連鎖関係で箱を分ける。
このグループの数が爆弾の数より少ないならすべての箱を開けることができる。
そのようになる箱の分け方の場合の数を求めて(箱の数)!で割ればいい。
ステージ2:
”DP[箱の数][グループの数]=分け方”というDPを考える。
DP[1][1]=1は明らか
DP[i][j]は1:箱iが1つで1グループを形成する場合がDP[i-1][j-1]
2:箱iが他のグループに入り込む場合は(i-1)*DP[i-1][j]
       (i-1個の箱ををj個のグループに分けたあと箱iを押し込む)
ステージ3:
規約分数にするために最大公約数で割る

#include <string>
#include <sstream>

typedef long long LL;

class KeysInBoxes 
{
	public:

		LL DP[30][30];

		LL gcd(LL a,LL b)
		{
			if(b==0)
				return a;
			else
				return gcd(b,a%b);
		}

		string getAllKeys(int N, int M) 
		{
			DP[1][1]=1;
			for(int i=2;i<=N;i++)
				for(int j=1;j<=M;j++)
					DP[i][j]=DP[i-1][j-1]+(i-1)*DP[i-1][j];

			LL c=0;
			LL m=1;
			for(int i=1;i<=M;i++)
				c+=DP[N][i];
			for(int i=1;i<=N;i++)
				m*=i;
			LL g=gcd(c,m);
			c/=g,m/=g;
			stringstream ss;
			ss << c << "/" << m;

			return ss.str();
		}
};