# 某島

… : "…アッカリ～ン . .. . " .. .
May 10, 2020

## 275

（x <= 1e5, y <= 1e9）

## 950

NIM 取子遊戲，Bob 可以修改初始的狀態，挑選出一些 pile 加石子，

```/* &*#()&*#)&E*F& */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}

/* -&\$&#*( &#*@)^\$@&*)*/

const int MOD = 1000000007;
const int INF = 0x7fffffff;

const int N = 1000;
int n = 1000;

DB dp[2][N+1][N+1];
DB u;

int low_bit(int x){
return x & -x;
}

void Modify(int p, int x, int y){
while (x > 0){
for (int t = y; t > 0; t -= low_bit(t))
dp[p][x][t] += u;
x -= low_bit(x);
}
}

DB Query(int p, int x, int y){
DB res = 0; while (x <= n){
for (int t = y; t <= n; t += low_bit(t))
res += dp[p][x][t];
x += low_bit(x);
}
return res;
}

class EllysTwoRatings {
public:
double getChance(int NN, int A, int B) {
RST(dp); int p = 1, q = 0;
int x1 = A, x2 = A, y1 = B, y2 = B;

u = 1;
Modify(p, x2, y2);
Modify(p, x1-1, y1-1);
u = -u;
Modify(p, x2, y1-1);
Modify(p, x1-1, y2);

cout << Query(p, A,B) << endl;

DB z = 0;

REP(i, NN) {
swap(p, q); RST(dp[p]);

REP_1(a,N) REP_1(b,N){
u = Query(q, a, b);
//DB u = dp[q][a][b]
if (a == b) {
z += u;
continue;
}
if (u <= 1e-9) continue;

int x1 = a - 100; checkMax(x1, 1);
int x2 = a + 100; checkMin(x2, N);
int y1 = b - 100; checkMax(y1, 1);
int y2 = b + 100; checkMin(y2, N);

u /= (DB)(x2-x1+1)*(y2-y1+1);
Modify(p, x2, y2);
Modify(p, x1-1, y1-1);
u = -u;
Modify(p, x2, y1-1);
Modify(p, x1-1, y2);
/*
FOR_1(a, a0, x2) FOR_1(b, b0, b1) {
dp[p][a][b] += u;
}*/
}
}

REP_1(j, N) z += Query(p, j, j);
return z;
}
};

// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}

int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}

if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}

static const double MAX_DOUBLE_ERROR = 1e-9; static bool topcoder_fequ(double expected, double result) { if (isnan(expected)) { return isnan(result); } else if (isinf(expected)) { if (expected > 0) { return result > 0 && isinf(result); } else { return result < 0 && isinf(result); } } else if (isnan(result) || isinf(result)) { return false; } else if (fabs(result - expected) < MAX_DOUBLE_ERROR) { return true; } else { double mmin = min(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); double mmax = max(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); return result > mmin && result < mmax; } }
double moj_relative_error(double expected, double result) { if (isnan(expected) || isinf(expected) || isnan(result) || isinf(result) || expected == 0) return 0; return fabs(result-expected) / fabs(expected); }

int verify_case(int casenum, const double &expected, const double &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";

string verdict;
vector<string> info;
char buf[100];

if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}

verdict = "PASSED";
if (rerr > 0) {
sprintf(buf, "relative error %.3e", rerr);
info.push_back(buf);
}
} else {
verdict = "FAILED";
}

cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;

if (verdict == "FAILED") {
cerr << "    Expected: " << expected << endl;
}

return verdict == "PASSED";
}

int run_test_case(int casenum) {
switch (casenum) {
case 0: {
int N                     = 13;
int A                     = 42;
int B                     = 666;
double expected__         = 0.001968164704;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}
case 1: {
int N                     = 3;
int A                     = 1;
int B                     = 1000;
double expected__         = 0.0;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}
case 2: {
int N                     = 20;
int A                     = 216;
int B                     = 219;
double expected__         = 0.083322288706;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}
case 3: {
int N                     = 42;
int A                     = 973;
int B                     = 123;
double expected__         = 0.019345240789;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}

// custom cases

/*      case 4: {
int N                     = ;
int A                     = ;
int B                     = ;
double expected__         = ;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}*/
/*      case 5: {
int N                     = ;
int A                     = ;
int B                     = ;
double expected__         = ;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}*/
/*      case 6: {
int N                     = ;
int A                     = ;
int B                     = ;
double expected__         = ;

clock_t start__           = clock();
double received__         = EllysTwoRatings().getChance(N, A, B);
}*/
default:
return -1;
}
}
}

int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE

```