Submission #1390005


Source Code Expand

// 基本テンプレート (縮小版)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

// 行列ライブラリ
// Verified: TopCoder SRM 704 Div.2 (ModEquationEasy)
// 行列の積 と 累乗(繰り返し二乗法)

// Matrix Library Begin (C++11)

template <typename T>
using Matrix = vector< vector<T> >;

template <typename T>
void init_mat(Matrix<T> &A, int h, int w) {
    A.resize(h, vector<T>(w, 0));
}

template <typename T>
Matrix<T> calc_mat(Matrix<T> A, Matrix<T> B) {
    Matrix<T> C(A.size(), vector<T>(B[0].size()));
    for(int i=0; i<A.size(); i++) {
        for(int k=0; k<B.size(); k++) {
            for(int j=0; j<B[0].size(); j++) {
                C[i][j] += A[i][k] * B[k][j]; // modなし
                // C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; // modあり
            }
        }
    }
    return C;
}

template <typename T>
Matrix<T> mat_pow(Matrix<T> A, ll n) {
    Matrix<T> B(A.size(), vector<T>(A.size()));
    for(int i=0; i<A.size(); i++) B[i][i] = 1;
    while(n > 0) {
        if(n & 1) B = calc_mat(B, A);
        A = calc_mat(A, A);
        n >>= 1;
    }
    return B;
}

// Matrix Library End

signed main() {
    double p; int n; cin >> p >> n;
    Matrix<double> mat;
    init_mat(mat, 2, 2);
    mat = { {1.0-p, p}, {p, 1.0-p} };
    mat = mat_pow(mat, n);
    printf("%.12f\n", mat[1][0]);
    return 0;
}

Submission Info

Submission Time
Task A - eject
User tsutaj
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1906 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 23
WA × 10
Set Name Test Cases
All 00-sample-00, 00-sample-01, 10-random_small-00, 10-random_small-01, 10-random_small-02, 10-random_small-03, 10-random_small-04, 10-random_small-05, 10-random_small-06, 10-random_small-07, 10-random_small-08, 10-random_small-09, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 20-random_large-05, 20-random_large-06, 20-random_large-07, 20-random_large-08, 20-random_large-09, 30-p_zero-00, 30-p_zero-01, 30-p_zero-02, 30-p_zero-03, 30-p_zero-04, 40-p_one-00, 40-p_one-01, 40-p_one-02, 40-p_one-03, 40-p_one-04, 90-handmade-00
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
10-random_small-00 AC 1 ms 256 KB
10-random_small-01 AC 1 ms 256 KB
10-random_small-02 AC 1 ms 256 KB
10-random_small-03 AC 1 ms 256 KB
10-random_small-04 AC 1 ms 256 KB
10-random_small-05 AC 1 ms 256 KB
10-random_small-06 AC 1 ms 256 KB
10-random_small-07 AC 1 ms 256 KB
10-random_small-08 AC 1 ms 256 KB
10-random_small-09 AC 1 ms 256 KB
20-random_large-00 WA 1 ms 256 KB
20-random_large-01 WA 1 ms 256 KB
20-random_large-02 WA 1 ms 256 KB
20-random_large-03 WA 1 ms 256 KB
20-random_large-04 WA 1 ms 256 KB
20-random_large-05 WA 1 ms 256 KB
20-random_large-06 WA 1 ms 256 KB
20-random_large-07 WA 1 ms 256 KB
20-random_large-08 WA 1 ms 256 KB
20-random_large-09 WA 1 ms 256 KB
30-p_zero-00 AC 1 ms 256 KB
30-p_zero-01 AC 1 ms 256 KB
30-p_zero-02 AC 1 ms 256 KB
30-p_zero-03 AC 1 ms 256 KB
30-p_zero-04 AC 1 ms 256 KB
40-p_one-00 AC 1 ms 256 KB
40-p_one-01 AC 1 ms 256 KB
40-p_one-02 AC 1 ms 256 KB
40-p_one-03 AC 1 ms 256 KB
40-p_one-04 AC 1 ms 256 KB
90-handmade-00 AC 1 ms 256 KB