ZOJ 3329 One Person Game 带环的概率DP

每次都和e[0]有关系 通过方程消去环

dp[i] = sigma(dp[i+k]*p)+dp[0]*p+1
dp[i] = a[i]*dp[0]+b[i]
dp[i] = sigma(p*(a[i+k]*dp[0]+b[i+k]))+dp[0]*p+1
a[i] = sigma(a[i+k]*p)+p
b[i] = sigma(b[i+k]*p)+1

#include <cstdio>
#include <cstring>
using namespace std;
double A[555], B[555], P[555];
//dp[i] = sigma(dp[i+k]*p)+dp[0]*p+1
//dp[i] = a[i]*dp[0]+b[i]
//dp[i] = sigma(p*(a[i+k]*dp[0]+b[i+k]))+dp[0]*p+1
//a[i] = sigma(a[i+k]*p)+p
//b[i] = sigma(b[i+k]*p)+1
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);memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));memset(P, 0, sizeof(P));double p = 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)P[i+j+k] += p;for(int i = n; i >= 0; i--){A[i] = p;B[i] = 1;for(int j = 1; j <= k1+k2+k3; j++){A[i] += A[i+j]*P[j];B[i] += B[i+j]*P[j];}}printf("%.18lf\n", B[0]/(1-A[0]));}return 0;
}