SRM304 div1 medium

何個のサイコロがvを出すかの組み合わせで分ける

#include <algorithm>

using namespace std;

double cache[2500+10][50+10];

class Conditional 
{
	public:

		int v;
		int maxSide;
		double C[55][55];

		double rec(int sum,int nD)
		{
			if(sum<=0)
				return 1.0;
			else if(nD==0)
				return 0.0;
			else
			{
				double &r=cache[sum][nD];
				if(!(r<-1.0))
					return r;
				r=0.0;
				for(int i=1;i<=maxSide;i++)
					if(i!=v)
						r+=rec(sum-i,nD-1)/(double)(maxSide-1);
				return r;
			}
		}

		double probability(int nDice, int _maxSide, int _v, int theSum) 
		{
			v=_v;
			maxSide=_maxSide;
			for(int i=0;i<55;i++)
				for(int j=0;j<55;j++)
					C[i][j]=(i==0 || j==0)?1.0:C[i-1][j]+C[i][j-1];
			double m=0,ans=0;
			fill(&cache[0][0],&cache[2500+10-1][50+10-1],-2.0);
			for(int i=1;i<=nDice;i++)
				m+=C[nDice-i][i]*pow(double(maxSide-1),double(nDice-i));
			for(int i=1;i<=nDice;i++)
				ans+=C[nDice-i][i]*pow(double(maxSide-1),double(nDice-i))*rec(theSum-v*i,nDice-i);

			return ans/m;
		}
};