Contest Duration: - (local time) (90 minutes)

Submission #273403

Source Code Expand

Copy
```#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <cmath>
#include <complex>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>
#include <valarray>
#include <list>

using namespace std;

typedef long long ll;

template<class T>
struct Pi {
T x, y;
Pi() {}
Pi(T xx, T yy) {
x = xx; y = yy;
}
bool operator<(const Pi &r) const {
if (x != r.x) return x < r.x;
return y < r.y;
}
bool operator>(const Pi &r) const {
if (x != r.x) return x > r.x;
return y > r.y;
}
bool operator==(const Pi &r) const {
if (x != r.x) return false;
return y == r.y;
}
};

template<class T>
struct Ti {
T x, y, z;
Ti() {}
Ti(T xx, T yy, T zz) {
x = xx; y = yy; z = zz;
}
bool operator<(const Ti &r) const {
if (x != r.x) return x < r.x;
if (y != r.y) return y < r.y;
return z < r.z;
}
bool operator>(const Ti &r) const {
if (x != r.x) return x > r.x;
if (y != r.y) return y > r.y;
return z > r.z;
}
bool operator==(const Ti &r) const {
if (x != r.x) return false;
if (y != r.y) return false;
return z == r.z;
}
};

struct SMatrix {
typedef double D;
vector<valarray<D>> d;
int N, M;
SMatrix(int n, int m) {
N = n; M = m;
d.resize(n);
for (int i = 0; i < N; i++) {
d[i] = valarray<D>(D(0), m);
}
}

valarray<D>& operator[](int p) {
return d[p];
}

const valarray<D>& operator[](int p) const {
return d[p];
}

SMatrix& operator=(const SMatrix &other) {
assert(other.N == N && other.M == M);
copy_n(other.d.begin(), N, d.begin());
return *this;
}

SMatrix operator+(const SMatrix &right) {
assert(right.N == N && right.M == M);
SMatrix res(N, M);
for (int i = 0; i < N; i++) {
res[i] = d[i]+right[i];
}
return res;
}

SMatrix operator*(const SMatrix &right) {
assert(M == right.N);
SMatrix res(N, right.M), r(right.M, right.N);
for (int i = 0; i < right.M; i++) {
for (int j = 0; j < right.N; j++) {
r[i][j] = right[j][i];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < right.M; j++) {
res[i][j] = (d[i]*r[j]).sum();
}
}
return res;
}

SMatrix operator*(const D x) {
SMatrix res(N, M);
for (int i = 0; i < N; i++) {
res[i] = d[i]*x;
}
return res;
}

SMatrix pow(ll p) {
assert(N == M);
SMatrix res(N, M), buf = *this;
for (int i = 0; i < N; i++) res[i][i] = D(1);
while(p != 0) {
if (p % 2) {
res = res*buf;
}
p /= 2;
buf = buf*buf;
}
return res;
}
};

int main() {
double p;
ll n;
cin >> p >> n;
SMatrix m = SMatrix(2, 2);
m[0][0] = 1-p;
m[0][1] = p;
m[1][0] = p;
m[1][1] = 1-p;
m = m.pow(n);
printf("%.20f\n", m[0][1]);
return 0;
}
```

#### Submission Info

Submission Time 2014-11-09 09:16:45+0900 A - eject yosupo C++11 (GCC 4.8.1) 0 3505 Byte WA 25 ms 928 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 22 ms 804 KB
00-sample-01 AC 20 ms 920 KB
10-random_small-00 AC 25 ms 928 KB
10-random_small-01 AC 21 ms 928 KB
10-random_small-02 AC 23 ms 800 KB
10-random_small-03 AC 23 ms 804 KB
10-random_small-04 AC 23 ms 736 KB
10-random_small-05 AC 21 ms 672 KB
10-random_small-06 AC 23 ms 728 KB
10-random_small-07 AC 23 ms 800 KB
10-random_small-08 AC 22 ms 800 KB
10-random_small-09 AC 21 ms 796 KB
20-random_large-00 WA 21 ms 800 KB
20-random_large-01 WA 23 ms 800 KB
20-random_large-02 WA 22 ms 800 KB
20-random_large-03 WA 24 ms 804 KB
20-random_large-04 WA 22 ms 796 KB
20-random_large-05 WA 22 ms 676 KB
20-random_large-06 WA 23 ms 748 KB
20-random_large-07 WA 24 ms 700 KB
20-random_large-08 WA 23 ms 804 KB
20-random_large-09 WA 22 ms 924 KB
30-p_zero-00 AC 24 ms 800 KB
30-p_zero-01 AC 23 ms 800 KB
30-p_zero-02 AC 23 ms 808 KB
30-p_zero-03 AC 23 ms 920 KB
30-p_zero-04 AC 21 ms 928 KB
40-p_one-00 AC 20 ms 924 KB
40-p_one-01 AC 23 ms 732 KB
40-p_one-02 AC 24 ms 796 KB
40-p_one-03 AC 21 ms 804 KB
40-p_one-04 AC 21 ms 796 KB
90-handmade-00 AC 23 ms 736 KB