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