Submission #149651

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <cstdlib>
#include <numeric>
#include <bitset>
#include <cstring>
#include <iomanip>
using namespace std;

#define REP(i, m, n) for(int i=(m); i<int(n); ++i)
#define rep(i, n) for(int i=0; i<int(n); ++i)
#define each(it, a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
//#define FILL(a, c) std::fill((__typeof(c)*)(a), (__typeof(c)*)(a) + sizeof(a) / sizeof(__typeof(c)), (c))
#define FILL(a, c) fill_n(reinterpret_cast<__typeof(c)*>(a), sizeof(a) / sizeof(__typeof(c)), (c))
template<class T> void fill_n(const T *first, size_t n, const T &value) { for(; n>0; --n) *const_cast<T*>(first++) = value; }
#define pb push_back                                                                          
#define mp make_pair
#define def(a, x) __typeof(x) a = x
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> PI;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};


vector<double> companion_mult(const vector<double> &coeff, const vector<double> &u, const vector<double> &v) {
	const int k = sz(coeff)-1;
	vector<double> c(k*2, 0);
	rep(i, k) rep(j, k) c[i+j] += u[i] * v[j];
	double z = u[k];
	rep(i, k) z += u[i] * v[k];
	for(int i=k*2-1; i>=k; i--) rep(j, k+1) (j==k ? z : c[i-k+j]) += c[i] * coeff[j];
	c.resize(k+1);
	c[k] = z;
	return c;
}
double solve_recursion_with_const(const vector<double> &coeff, const vector<double> &init, ll p) {
	const int k = sz(init);
	assert(p >= 0 && k+1 == sz(coeff) && k >= 1);
	vector<double> x(k+1, 0), b(k+1, 0);
	x[0] = 1;
	if (k == 1) b = coeff; else b[1] = 1;
	for(; p > 0; p>>=1, b = companion_mult(coeff, b, b)) if (p&1) x = companion_mult(coeff, x, b);
	double res = x[k];
	rep(i, k) res += init[i] * x[i];
	return res;
}
int main() {
	double p, q, r;
	cin >> p >> q >> r;
	double s = p+q+r;
	ll N, K, M;
	cin >> N >> K >> M;
	vector<double> coeff(N*K+1, 0);
	coeff[0] += r/s;
	coeff[N*K-N] += p/s;
	coeff[N*K-1] += q/s;
	coeff[N*K] += 1.0/s;
	double res = solve_recursion_with_const(coeff, vector<double>(N*K, 0.0), M*N+N*K-1);
	printf("%.20f\n", res);
}

Submission Info

Judge Result