方程很明显有
d[i]=sum(pk*d[i+k])+p0*d[0];
其中pi可以在开始时枚举求出。
设d[i]=A[i]*d[0]+B[i],
代入上式
d[i]=(sum(pk*A[i+k])+p0)+sum(pk*B[i+k])+1
可得
A[i]=sum(pk*A[i+k])+p0
B[i]=sum(pk*B[i+k])+1
这种设系数方法好像挺常用挺经典的。在HDU 的MAZE也有用这种方法的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double A[600],B[600];
double p[20];
int main(){
int T;
int n,k1,k2,k3,a,b,c;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
memset(p,0,sizeof(p));
double p0=1.0/(k1*k2*k3);
for(int i=1;i<=k1;i++){
for(int j=1;j<=k2;j++){
for(int k=1;k<=k3;k++)
if(i==a&&j==b&&k==c)
continue;
else p[i+j+k]+=p0;
}
}
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
for(int i=n;i>=0;i--){
A[i]=p0;B[i]=1;
for(int j=1;j<=k1+k2+k3;j++){
A[i]+=p[j]*A[i+j];
B[i]+=p[j]*B[i+j];
}
}
printf("%.15lf\n",B[0]/(1-A[0]));
}
return 0;
}