#ifdef ONLINE_JUDGE
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//using ld = long double;

constexpr int ITERS = 100;
constexpr double one = 1;
constexpr double hundred = 100;

vector<vector<double>> pow(vector<vector<double>> m1, vector<vector<double>> m2) {
    vector<vector<double>> m3(3, vector<double>(3));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                m3[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    for (int i = 0; i < 3; ++i) {
        double sum = m3[i][0] + m3[i][1] + m3[i][2];
        for (int j = 0; j < 3; ++j) {
            m3[i][j] = m3[i][j] / sum;
        }
    }
    return m3;
}

vector<vector<double>> binpow(vector<vector<double>> m) {
    for (int i = 0; i < ITERS; ++i) m = pow(m, m);
    return m;
}

vector<double> vecMul(vector<vector<double>> m, vector<double> p) {
    return {
        p[0] * m[0][0] + p[1] * m[1][0] + p[2] * m[2][0],
        p[0] * m[0][1] + p[1] * m[1][1] + p[2] * m[2][1],
        p[0] * m[0][2] + p[1] * m[1][2] + p[2] * m[2][2]
    };
}



//FFT
//using comp = complex<double>;
//const double PI = acos(-1);
//
//constexpr double PI2 = 6.283185307179586;
//
//void fft(vector<comp>& a, vector<comp>& res, int n, comp x, int abg, int astep, int rbg) {
//    if (n == 1) {
//        res[rbg] = a[abg];
//        return;
//    }
//    fft(a, res, n / 2, x * x, abg, astep * 2, rbg);
//    fft(a, res, n / 2, x * x, abg + astep, astep * 2, rbg + n / 2);
//    comp w = 1;
//    for (int i = 0; i < n/2; ++i) {
//        comp rc = res[rbg + i];
//        comp rd = res[rbg + i + n / 2];
//        res[rbg + i] = rc + w * rd;
//        res[rbg + i + n / 2] = rc - w * rd;
//        w *= x;
//    }
//}
//
//int log2(int x) {
//    int res = 31 - __builtin_clz(x);
//    if (1 << res < x) res++;
//    return res;
//}
//
//vector<double> mult(vector<double>& aReference, vector<double>& bReference) {
//    int n = 1 << log2(int(aReference.size() + bReference.size()));
//    vector<comp> ra(n), rb(n), a(aReference.begin(), aReference.end()), b(bReference.begin(), bReference.end());
//    a.resize(n, 0), b.resize(n, 0);
//    comp x = comp(cos(2 * PI / n), sin(2 * PI / n));
//    fft(a, ra, n, x, 0, 1, 0);
//    fft(b, rb, n, x, 0, 1, 0);
//    vector<comp> rab(n);
//    for (int i = 0; i < n; ++i) rab[i] = ra[i] * rb[i] / comp(n);
//    x = comp(cos(2 * PI / n), -sin(2 * PI / n));
//    vector<comp> c(n);
//    fft(rab, c, n, x, 0, 1, 0);
//    vector<double> cc(n);
//    for (int i = 0; i < n; i++) cc[i] = c[i].real();
//    return cc;
//}




using comp = complex<double>;
const double PI = acos(-1);

int log2(int x) {
    int res = 31 - __builtin_clz(x);
    if (1 << res < x) res++;
    return res;
}

constexpr double PI2 = 6.283185307179586;
const int LG = 18;
const int R = 1 << LG;

comp pa[R], pb[R];
vector<int> rev[LG+1];
double result[R];
vector<comp> pw[LG+1], pwi[LG+1];

inline void fft(comp a[], int r, int lg) {
    for (int i = 0; i < r; ++i) {
        if (i < rev[lg][i]) {
            swap(a[i], a[rev[lg][i]]);
        }
    }
    for (int lgi = 1; lgi <= lg; lgi++) {
        int l = 1 << lgi;
        for (int i = 0; i < r; i += l) {
            comp t;
            comp *p1 = a + i, *p2 = a + i + (l >> 1);
            comp *pe = a + i + (l >> 1);
            auto ppw = pw[lgi].begin();
            while (p1 != pe) {
                t = *p2 * *ppw;
                *p2 = *p1 - t;
                *p1 += t;
                ++p1;
                ++p2;
                ++ppw;
            }
        }
    }
}

inline void ifft(comp a[], int r, int lg) {
    for (int i = 0; i < r; ++i) {
        if (i < rev[lg][i]) {
            swap(a[i], a[rev[lg][i]]);
        }
    }
    for (int lgi = 1; lgi <= lg; lgi++) {
        int l = 1 << lgi;
        for (int i = 0; i < r; i += l) {
            comp t;
            comp *p1 = a + i, *p2 = a + i + (l >> 1);
            comp *pe = a + i + (l >> 1);
            auto ppw = pwi[lgi].begin();
            while (p1 != pe) {
                t = *p2 * *ppw;
                *p2 = *p1 - t;
                *p1 += t;
                ++p1;
                ++p2;
                ++ppw;
            }
        }
    }
    for (int i = 0; i < r; ++i) a[i] /= r;
}

vector<double> mult(vector<double>& a, vector<double>& b) {
    int r = int(a.size() + b.size());
    int lg = log2(r);
    r = 1 << lg;
    int sizeNow = (sizeof(pa) / R) * r;
    
    for (int i = 0; i < a.size(); ++i) pa[i] = a[i];
    for (int i = 0; i < b.size(); ++i) pb[i] = b[i];
    
    fft(pa, r, lg);
    fft(pb, r, lg);
    
    for (int i = 0; i < r; ++i) pa[i] *= pb[i];
    ifft(pa, r, lg);
    
    vector<double> result(a.size() + b.size() - 1);
    for (int i = 0; i + 1 < a.size() + b.size(); ++i) result[i] += pa[i].real();
    
    memset(pa, 0, sizeNow);
    memset(pb, 0, sizeNow);
    
    return result;
}

inline void precalc() {
    for (int lg = 2; lg <= LG; ++lg) {
        int r = 1 << lg;
        rev[lg].resize(r);
        for (int i = 0; i < r; ++i) {
            for (int b = 0; b < lg; ++b) {
                rev[lg][i] |= ((i >> b) & 1) << (lg - b - 1);
            }
        }
    }
    
    for (int lgi = 1; lgi <= LG; lgi++) {
        int l = 1 << lgi;
        pw[lgi].resize(l);
        comp wn = comp(cos(PI2 / l), sin(PI2 / l));
        pw[lgi][0] = comp(1, 0);
        for (int i = 1; i < l >> 1; ++i) pw[lgi][i] = pw[lgi][i - 1] * wn;
    }
    
    for (int lgi = 1; lgi <= LG; lgi++) {
        int l = 1 << lgi;
        pwi[lgi].resize(l);
        comp wn = comp(cos(-PI2 / l), sin(-PI2 / l));
        pwi[lgi][0] = comp(1, 0);
        for (int i = 1; i < l >> 1; ++i) pwi[lgi][i] = pwi[lgi][i - 1] * wn;
    }
}






vector<double> solve(const vector<double>& v, int l, int r) {
    if (r-l == 1) {
        return {double(1) - v[l], v[l]};
    } else {
        int m = (l + r) >> 1;
        vector<double> a = solve(v, l, m), b = solve(v, m, r);
        return mult(a, b);
    }
}


signed main() {
    precalc();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << setprecision(10) << fixed;
    
    int n;
    cin >> n;
    vector<double> ppp[3];
    for (int i = 0; i < 3; ++i) ppp[i].resize(n, 0);
    
    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c, --c;
        vector<vector<double>> go(3, vector<double>(3));
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                int z;
                cin >> z;
                go[j][k] = double(z) / hundred;
            }
        }
        vector<double> p(3, 0);
        p[c] = 1;
        auto big = binpow(go);
        for (int j = 0; j < 6; ++j) {
            auto result = vecMul(big, p);
            for (int k = 0; k < 3; ++k) ppp[k][i] += result[k];
            big = pow(big, go);
        }
        for (int k = 0; k < 3; ++k) ppp[k][i] /= 6;
    }
    
    int E = n/2 + 1;
    double answer = 0;
    
    for (int i = 0; i < 3; ++i) {
        auto result = solve(ppp[i], 0, n);
        for (int j = E; j <= n; ++j) answer += result[j];
//        for (int j = 1; j <= n; ++j) cout << result[j] << " ";
//        cout << endl;
    }
    
//    cout << "--" << endl;
//    double dp[n+1][n+1];
//    for (int i = 0; i < 3; ++i) {
//        memset(dp, 0, sizeof(dp));
//        dp[0][0] = 1;
//        for (int j = 1; j <= n; ++j) {
//            for (int k = 0; k <= j; ++k) {
//                dp[j][k] = (k > 0 ? dp[j-1][k-1] : 0) * ppp[i][j-1] + dp[j-1][k] * (one - ppp[i][j-1]);
//            }
//        }
//        for (int j = 1; j <= n; ++j) {
//            cout << dp[n][j] << ' ';
//        }
//        //for (int j = E; j <= n; ++j) answer += dp[n][j];
//        cout << endl;
//    }
    
    cout << answer << endl;
}
Can't compile file:
program.cpp: In function 'std::vector<double> mult(std::vector<double>&, std::vector<double>&)':
program.cpp:172:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long long unsigned int'} [-Wsign-compare]
  172 |     for (int i = 0; i < a.size(); ++i) pa[i] = a[i];
      |                     ~~^~~~~~~~~~
program.cpp:173:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long long unsigned int'} [-Wsign-compare]
  173 |     for (int i = 0; i < b.size(); ++i) pb[i] = b[i];
      |                     ~~^~~~~~~~~~
program.cpp:182:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long long unsigned int'} [-Wsign-compare]
  182 |     for (int i = 0; i + 1 < a.size() + b.size(); ++i) result[i] += pa[i].real();
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~~
program.cpp:184:11: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'using comp = class std::complex<double>' {aka 'class std::complex<double>'}; use assignment or value-initialization instead [-Wclass-memaccess]
  184 |     memset(pa, 0, sizeNow);
      |     ~~~~~~^~~~~~~~~~~~~~~~
In file included from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/ccomplex:39,
                 from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/x86_64-w64-mingw32/bits/stdc++.h:127,
                 from program.cpp:5:
C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/complex:1497:11: note: 'using comp = class std::complex<double>' {aka 'class std::complex<double>'} declared here
 1497 |     class complex<double>
      |           ^~~~~~~~~~~~~~~
program.cpp:185:11: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'using comp = class std::complex<double>' {aka 'class std::complex<double>'}; use assignment or value-initialization instead [-Wclass-memaccess]
  185 |     memset(pb, 0, sizeNow);
      |     ~~~~~~^~~~~~~~~~~~~~~~
C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/complex:1497:11: note: 'using comp = class std::complex<double>' {aka 'class std::complex<double>'} declared here
 1497 |     class complex<double>
      |           ^~~~~~~~~~~~~~~
In file included from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/string:43,
                 from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/bitset:52,
                 from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/x86_64-w64-mingw32/bits/stdc++.h:52:
C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/bits/allocator.h: In destructor 'constexpr std::_Vector_base<double, std::allocator<double> >::_Vector_impl::~_Vector_impl()':
C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = double]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/vector:66,
                 from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/functional:64,
                 from C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/x86_64-w64-mingw32/bits/stdc++.h:53:
C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |