2015
09-17

# Random Walk

Yuanfang is walking on a chain. The chain has n nodes numbered from 1 to n. Every second, he can move from node i to node j with probability:

c(i,j) is an element in a given parameter matrix which is n×m. (1 <= c(i, j) <= 9)
Yuanfang wants to know the expectation time for him to walk from node 1 to node n.

There are no more than 10 test cases.
In each case, there are two integers n (2 <= n <= 50000), m (1 <= m <= 5), in the first line, meaning that there are n nodes and the parameter matrix is n×m . There are m integers in each of the next n lines which describe the parameter matrix .
The input ends with 0 0.

There are no more than 10 test cases.
In each case, there are two integers n (2 <= n <= 50000), m (1 <= m <= 5), in the first line, meaning that there are n nodes and the parameter matrix is n×m . There are m integers in each of the next n lines which describe the parameter matrix .
The input ends with 0 0.

3 1
1
1
1
5 2
1 2
2 1
3 2
2 3
1 3
0 0

6.94
8.75

dp[i] = sigma(dp[i + j] * p (i , i + j)) + 1 .   (-m <= j <= m)

n个方程，n个变元，由于每个方程中的未知数不多，所以可以暴力消元。

O(n * m)的复杂度从大到小暴力消元。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 50005;
double p[N][11];
int n , m , c[11];
int l[N] , r[N];
double a[N][11];
double constant[N];
bool zero (double d) {
const double eps = 1e-6;
return fabs(d) < eps;
}
int main () {
#ifndef ONLINE_JUDGE
freopen ("input.txt" , "r" , stdin);
#endif
while (scanf ("%d %d" , &n, &m) != EOF) {
if (!n & !m) break;
for (int i = 1 ; i <= n ; i ++) {
int tot = 0;
for (int j = 1 ; j <= m ; j ++) {
scanf ("%d" , &c[j]);
tot += c[j];
}
double other = 1.0;
for (int j = -m ; j < 0 ; j ++) {
p[i][j + m] = 0.3 * c[-j] / (1 + tot);
if (i + j >= 1) other -= p[i][j + m];
}
for (int j = 1 ; j <= m ; j ++) {
p[i][j + m] = 0.7 * c[j] / (1 + tot);
if(i + j <= n) other -= p[i][j + m];
}
p[i][m] = other;
}
memset (a , 0 , sizeof(a));
for (int i = n - 1 ; i > 0 ; i --) {
l[i] = max(i - m , 1);
r[i] = min(n , i + m);
for (int j = 0 ; j < r[i] - l[i] + 1 ; j ++) {
a[i][j] = p[i][(l[i] + j) - i + m];
}
constant[i] = 1.0;
for (int j = r[i] ; j > i ; j --) {
if (j == n) a[i][j - l[i]] = 0;
else {
double q = a[i][j - l[i]];
if (zero(q)) continue;
for (int k = 0 ; k < j - l[j] ; k ++) {
a[i][k + l[j] - l[i]] += a[j][k] * q;
}
a[i][j - l[i]] = 0;
constant[i] += constant[j] * q;
}
}
double q = 1 - a[i][i - l[i]];
for (int j = 0 ; j < r[i] - l[i] + 1 ; j ++) {
a[i][j] = a[i][j] / q;
}
a[i][i - l[i]] = 0;
constant[i] = constant[i] / q;
}
printf ("%.2f\n" , constant[1]);
}
return 0;
}