Submission #2828546

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

// pretty print
// void mat_pp(vector<vector<long long>>& A) {
//     int n = A.size(), m = A[0].size();
//     printf("_ matrix %dx%d\n", n, m);
//     for (int i=0; i<n; ++i) {
//         for (int j=0; j<m; ++j) {
//             printf(" %5lld", A[i][j]);
//         }
//         printf("\n");
//     }
// }
template <typename T>
void mat_pp(vector<vector<T>>& A) {
    int n = A.size(), m = A[0].size();
    fprintf(stderr, "_ matrix %dx%d\n", n, m);
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            fprintf(stderr, " %5g", (double)A[i][j]);
        }
        fprintf(stderr, "\n");
    }
}

// assign
template <typename T>
void mat_assign(vector<vector<T>>& dest, vector<vector<T>>& src) {
    int n = src.size(), m = src[0].size();
    dest.resize(n);
    for (int i=0; i<n; ++i) {
        dest[i] = src[i];
    }
}

template <typename T>
void mat_assign_zero(vector<vector<T>>& dest, int n, int m) {
    dest.resize(n);
    for (int i=0; i<n; ++i) {
        dest[i].assign(m, (T)0);
    }
}

template <typename T>
void mat_assign_eye(vector<vector<T>>& dest, int n) {
    dest.resize(n);
    for (int i=0; i<n; ++i) {
        dest[i].assign(n, (T)0);
        dest[i][i] = (T)1;
    }
}

// mul
template <typename T>
void mat_assign_mul(vector<vector<T>>& dest, vector<vector<T>>& A, vector<vector<T>>& B) {
    int an = A.size(), am = A[0].size();
    int bn = B.size(), bm = B[0].size();
    assert(am == bn);
    // vector<vector<T>> C(an, vector<T>(bm, (T)0));
    // printf("* mat mul (%d %d)x(%d %d)\n", an,am, bn,bm);
    // mat_pp(A); mat_pp(B);

    mat_assign_zero(dest, an, bm);
    for (int i=0; i<an; ++i) {
        for (int j=0; j<bm; ++j) {
            for (int k=0; k<am; ++k) {
                dest[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    // mat_pp(dest);
}

template <typename T>
vector<vector<T>> mat_mul(vector<vector<T>>& A, vector<vector<T>>& B) {
    int an = A.size(), am = A[0].size();
    int bn = B.size(), bm = B[0].size();
    assert(am == bn);
    vector<vector<T>> C; // (an, vector<T>(bm, (T)0));
    mat_assign_mul(C, A, B);
    return C;
}

template <typename T>
void mat_s_mul(vector<vector<T>>& A, vector<vector<T>>& B) {
    int an = A.size(), am = A[0].size();
    int bn = B.size(), bm = B[0].size();
    assert(am == bn);

    vector<vector<T>> A_copy;
    mat_assign(A_copy, A);
    mat_assign_mul(A, A_copy, B);
}

template <typename T>
void mat_s_pow2(vector<vector<T>>& A) {
    int an = A.size(), am = A[0].size();
    assert(an == am);

    vector<vector<T>> A_copy;
    mat_assign(A_copy, A);
    mat_assign_mul(A, A_copy, A_copy);
}

template <typename T>
vector<T> mat_mul(vector<vector<T>>& A, vector<T>& x) {
    int an = A.size(), am = A[0].size();
    int xn = x.size();
    assert(am == xn);
    vector<T> y(an, (T)0);
    for (int i=0; i<an; ++i) {
        for (int k=0; k<am; ++k) {
            y[i] += A[i][k] * x[k];
        }
    }
    return y;
}


template <typename T>
vector<vector<T>> mat_pow(vector<vector<T>>& A, long long p=2) { // A^p
    int an = A.size(), am = A[0].size();
    assert(an == am);
    // printf("mat pow\n");
    // mat_pp(A);
    // printf("^ %lld =\n", p);

    if (p == 0) {
        vector<vector<T>> E;
        mat_assign_eye(E, an);
        // mat_pp(E);
        return E;
    }

    vector<vector<T>> U;
    mat_assign(U, A);
    if (p == 1) {
        // mat_pp(U);
        return U;
    }

    vector<vector<T>> R;
    mat_assign_eye(R, an);

    while (p) {
        if (p % 2) {
            mat_s_mul(R, U); // v *= u
            --p;
        } else {
            mat_s_pow2(U); // u ^= 2
            p /= 2;
        }
    }
    // mat_pp(R);
    return R;
}


// typedef long double Double;
typedef double Double;
typedef vector<Double> vD;
typedef vector<vector<Double>> vvD;

Double solve(int n,int m,int d){
    Double w0 = 0, w1 = 0, w2 = 0;
    if (d == 0) {
        w1 = 1.0;
    } else if (d*2 < n) {
        w1 = (Double)2*d/n; w2 = 1.0 - w1;
    } else if (d*2 == n) {
        w1 = 1.0;
    } else { // d*2 > n
        w1 = (Double)2*(n-d)/n; w0 = 1.0 - w1;
    }
    vvD A = {
         {w0,w0,w0, 0},
         {w1,w1,w1, 0},
         {w2,w2,w2, 0},
         { 0, 1.0/n, 2.0/n, 1}};
    vD x = {w0,w1,w2, 0};
#ifdef DEBUG
    cerr << "A=" << endl;
    mat_pp(A);
    cerr << "x=" << x << endl;
#endif
    vvD Ak = mat_pow(A, m-1);
    vD y = mat_mul(Ak, x);
#ifdef DEBUG
    cerr << "A^(m-1)=" << endl;
    mat_pp(Ak);
    cerr << "y=" << y << endl;
#endif
    return y.back();
}

int main() {
    int n,m,d; cin >>n>>m>>d;
    Double ans = solve(n,m,d);
    printf("%.10f\n", (double)ans);
    return 0;
}

Submission Info

Submission Time
Task C - Ordinary Beauty
User naoya_t
Language C++14 (GCC 5.4.1)
Score 300
Code Size 5012 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_1000000000_180707_0.txt, sample_2_3_1.txt
All 300 / 300 sample_1000000000_180707_0.txt, sample_2_3_1.txt, test_11936238_9_153932.txt, test_138666_2854897_1404.txt, test_1_2_0.txt, test_234679769_107_69508.txt, test_25213539_11160_27040.txt, test_28367_3200917_12993.txt, test_46387542_48_441879.txt, test_50484_560629_534.txt, test_569_56_8.txt, test_77_143_1.txt, test_8180059_850_58.txt
Case Name Status Exec Time Memory
sample_1000000000_180707_0.txt 1 ms 256 KB
sample_2_3_1.txt 1 ms 256 KB
test_11936238_9_153932.txt 1 ms 256 KB
test_138666_2854897_1404.txt 1 ms 256 KB
test_1_2_0.txt 1 ms 256 KB
test_234679769_107_69508.txt 1 ms 256 KB
test_25213539_11160_27040.txt 1 ms 256 KB
test_28367_3200917_12993.txt 1 ms 256 KB
test_46387542_48_441879.txt 1 ms 256 KB
test_50484_560629_534.txt 1 ms 256 KB
test_569_56_8.txt 1 ms 256 KB
test_77_143_1.txt 1 ms 256 KB
test_8180059_850_58.txt 1 ms 256 KB