Submission #103424

---

Source Code Expand

import java.io.*;
import java.util.*;
import java.lang.*;

class Reader {
    BufferedReader br;
    StringTokenizer st;
    Reader(InputStream is) {
	br = new BufferedReader(new InputStreamReader(is));
	st = null;
    }
    String next() {
	while (st == null || !st.hasMoreTokens()) {
	    try {
		st = new StringTokenizer(br.readLine());
	    } catch (Exception e) {
		e.printStackTrace();
	    }
	}
	return st.nextToken();
    }
    int nextInt() {
	return Integer.parseInt(next());
    }
    Long nextLong() {
	return Long.parseLong(next());
    }
    double nextDouble() {
	return Double.parseDouble(next());
    }
}

class Poly {
    double[] mul(double[] a, double[] b, double[] c) {
	int n = a.length;
	double[] r = new double[n*2];
	for (int i=0; i<n; i++) {
	    for (int j=0; j<n; j++) {
		r[i+j] = r[i+j] + a[i]*b[j];
	    }
	}
	for (int i=n*2; i-->n; ) {
	    for (int j=1; j<=n; j++) {
		r[i-j] = r[i-j] + r[i]*c[n-j];
	    }
	}
	double[] s = new double[n];
	System.arraycopy(r, 0, s, 0, n);
	return s;
    }
    double[] pow(double[] a, Long y, double[] c) {
	int n = a.length;
	double[] r = new double[n];
	r[0] = 1;
	for (; y > 0; y >>= 1) {
	    if ((y&1) == 1) r = mul(r, a, c);
	    a = mul(a, a, c);
	}
	return r;
    }
}

class Main {
    public static void main(String[] args) {
	new Main().solve();
    }
    void solve() {
	Reader in = new Reader(System.in);
	PrintStream out = System.out;

	double p = in.nextDouble();
	double q = in.nextDouble();
	double r = in.nextDouble();

	int N = in.nextInt();
	int K = in.nextInt();
	long M = in.nextLong();

	double[] v = new double[N*K+1];
	double base = p+q+r;

	v[0] += -r / base;
	v[1] += r / base;
	v[N*(K-1)] += -p / base;
	v[N*(K-1) + 1] += p / base;
	v[N*K-1] += -q / base;
	v[N*K] += (p + 2*q + r) / base;

	double[] alpha = new double[N*K+1];
	alpha[0] = 0;
	for (int i=1; i<=N*K; i++) {
	    alpha[i] = (i >= N ? p*alpha[i-N] : 0)
		+ (i >= 1 ? q*alpha[i-1] : 0)
		+ (i >= N*K ? r*alpha[i-N*K] : 0)
		+ 1.0;
	    alpha[i] /= base;
	}

	double[] beta = new double[N*K+1];
	beta[1] = 1;
	beta = new Poly().pow(beta, M*N, v);

	double ans = 0;
	for (int i=0; i<N*K+1; i++) ans += beta[i] * alpha[i];

	out.format("%.6f\n", ans);
    }
}

Submission Info

Judge Result