题意：有三个骰子，分别有k1,k2,k3个面。

每次掷骰子，如果三个面分别为a,b,c则分数置0，否则加上三个骰子的分数之和。

当分数大于n时结束。求游戏的期望步数。初始分数为0

思路： 本题通过代换系数，化简后求系数。

博客：http://www.cnblogs.com/jackge/archive/2013/05/21/3091839.html

/**
    dp求期望的题。
    题意：
    有三个均匀的骰子，分别有k1,k2,k3个面，初始分数是0，
    当掷三个骰子的点数分别为a,b,c的时候，分数清零，否则分数加上三个骰子的点数和，
    当分数>n的时候结束。求需要掷骰子的次数的期望。
    题解:
    设 E[i]表示现在分数为i，到结束游戏所要掷骰子的次数的期望值。
    显然 E[>n] = 0; E[0]即为所求答案;
    E[i] = ∑Pk*E[i+k] + P0*E[0] + 1; (Pk表示点数和为k的概率，P0表示分数清零的概率)
    由上式发现每个 E[i]都包含 E[0]，而 E[0]又是我们要求的，是个定值。
    设 E[i] = a[i]*E[0] + b[i];
    将其带入上面的式子：
    E[i] = ( ∑Pk*a[i+k] + P0 )*E[0] + ∑Pk*b[i+k] + 1;
    显然，
    a[i] = ∑Pk*a[i+k] + P0;
    b[i] = ∑Pk*b[i+k] + 1;
    当 i > n 时：
    E[i] = a[i]*E[0] + b[i] = 0;
    所以 a[i>n] = b[i>n] = 0;
    可依次算出 a[n],b[n]; a[n-1],b[n-1] ... a[0],b[0];
    则 E[0] = b[0]/(1 - a[0]);
**/             #include               #include                 #include                   #include                     #include                       using namespace std;double p[20],x[520],y[520];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n,k1,k2,k3,a,b,c;        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);        double p0=1.0/k1/k2/k3;        int tot=k1+k2+k3;        memset(x,0,sizeof(x));        memset(y,0,sizeof(y));        memset(p,0,sizeof(p));        for(int i=1;i<=k1;i++)            for(int j=1;j<=k2;j++)             for(int z=1;z<=k3;z++)            {            if(i!=a||j!=b||z!=c)            {                p[i+j+z]+=p0;            }            }        for(int i=n;i>=0;i--)         {             for(int k=1;k<=tot;k++)        {            x[i]+=x[i+k]*p[k];            y[i]+=y[i+k]*p[k];        }        x[i]+=p0;        y[i]+=1;         }         printf("%.15f\n",y[0]/(1.0-x[0]));    }    return 0;}