http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754
题意：有三个色子，分别有k1、k2、k3个面，权值分别是1～k1, 1~k2, 1~k3，等概率朝上。如果朝上的面分别为a、b、c，则分数置0，否则累加权值和。当权值和>n时则结束，求期望次数。T组数据。（T<=300; 1<k1,k2,k3<=6）
#include <cstdio>
#include <cstring>
using namespace std;
const int N=805;
double A[N], C[N];
int n, p[500], k1, k2, k3, a, b, c;
int main() {
int T, all, del;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d%d%d", &n, &k1, &k2, &k3, &a, &b, &c);
all=0;
del=a+b+c;
for(int i=1; i<=k1; ++i)
for(int j=1; j<=k2; ++j)
for(int k=1; k<=k3; ++k)
p[++all]=i+j+k;
for(int i=n; i>=0; --i) {
for(int j=1; j<=all; ++j) A[i]+=A[i+p[j]];
A[i]-=A[i+del]-1;
A[i]/=all;
for(int j=1; j<=all; ++j) C[i]+=C[i+p[j]];
C[i]-=C[i+del];
C[i]/=all;
C[i]+=1;
}
printf("%.15f
", C[0]/(1-A[0]));
memset(A, 0, sizeof(double)*(n+1));
memset(C, 0, sizeof(double)*(n+1));
}
return 0;
}
/*
A[i]=(sum_{j} A[j] - A[i+a+b+c] + 1)/(k1*k2*k3)
C[i]=(sum_{j} C[j] - C[i+a+b+c])/(k1*k2*k3) + 1
*/
设$d[i]$表示当前分数为$i$时到游戏结束的期望次数。容易推得公式：
$$d[i]=(sum_{j} d[j]-d[i+a+b+c]+d[0])/(k1*k2*k3)+1, j是转移到的状态$$
发现每一个都有一个循环的$d[0]$，那么我们可以将每一个状态表示为关于$d[0]$的方程的（在这里我是sb了没想到）
（如果不只是$d[0]$一个的话，那么最好用高斯消元）
所以我们只需要推系数即可！设$d[i]=A[i]d[0]+C[i]$
首先
$$
egin{align}
& sum_{j} d[j] - d[i+a+b+c] \
=& sum_{j} (A[j]d[0]+C[j]) - d[i+a+b+c] \
=& sum_{j} A[j]d[0] + sum_{j} C[j] - A[i+a+b+c]d[0]-C[i+a+b+c]
end{align}
$$
所以
$$d[i]=(d[0]sum_{j} A[j] + sum_{j} C[j] - A[i+a+b+c]d[0]-C[i+a+b+c] + d[0])/(k1*k2*k3)+1$$
所以
$$
egin{align}
A[i] = & (sum_{j} A[j] - A[i+a+b+c] + 1)/(k1*k2*k3)\
C[i] = & (sum_{j} C[j] - C[i+a+b+c])/(k1*k2*k3) + 1
end{align}
$$
最后答案是$d[0]=C[0]/(1-A[0])$