Submission #102354

---

Source Code Expand

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
typedef long long LL;

typedef vector<double> Poly;

// a*b where x^n = c
Poly mulPoly(const Poly&a, const Poly&b, const Poly&c) {
    int n=a.size();
    Poly r(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]);
        }
    }
    r.resize(n);
    return r;
}

Poly powPoly(Poly a, LL y, const Poly&c) {
    int n = a.size();
    Poly r(n);
    r[0]=1;
    for (;y; y>>=1) {
        if (y&1) r = mulPoly(r, a, c);
        a = mulPoly(a, a, c);
    }
    return r;
}


int main() {
    double p, q, r;
    LL N, K, M;
    cin >> p >> q >> r;
    cin >> N >> K >> M;

    vector<double> v(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;

    vector<double>alpha(N*K+1);
    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;
        alpha[i] /= base;
    }

    Poly beta(N*K+1);
    beta[1]=1;
    beta = powPoly(beta, N*M, v);

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

    printf("%.9f\n", ans);

    return 0;
}

Submission Info

Judge Result