http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754
本题分数为0的概率不确定,所以不能从0这端出发.
设E[i]为到达成功所需的步数,明显i>n时E[i]=0,当0<i<=n时E[i]=sigma(E[i+k]*pk)+E[0]*p0,(k是可以投出的除了恰为a,b,c以外的骰子之和),
在这个公式里,E[i]和E[0]都是未知的,设E[0]=x,则
E[i]=sigma(E[i+k]*pk)+x*p0+1,
因为比i大的所有j,满足E[j]的一次项和零次项都是已知的,明显,可以用x来表示所有E[i],
设E[i]的一次项部分为a[i],常数项部分为b[i],逐渐递推,可以得到E[0]=a[0]*E[0]+b[0],这时E[0]可解出,即为答案
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=;
const int maxk=;
double p[maxk*],dpa[maxn],dpb[maxn];
int n,k1,k2,k3,a,b,c;
int sumk;
double mulk;
void init(){
sumk=k1+k2+k3;
mulk=k1*k2*k3;
memset(p,,sizeof(p));
p[]=/mulk;
for(int i=; i<=k1; i++)
{
for(int j=; j<=k2; j++)
{
for(int k=; k<=k3; k++)
{
if(i!=a||j!=b||k!=c){ p[i+j+k]+=/(mulk);} }
}
}
}
void calc(){
for(int i=n;i>=;i--){
dpa[i]=p[];
dpb[i]=;
for(int j=;j<=sumk&&i+j<=n;j++){
dpa[i]+=dpa[i+j]*p[j];
dpb[i]+=dpb[i+j]*p[j];
}
}
}
int main()
{
int T;
scanf("%d",&T);
for(int ti=; ti<=T; ti++)
{
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
init();
calc();
printf("%.15f\n",dpb[]/(-dpa[]));
} return ;
}