# 某岛

… : "…アッカリ～ン . .. . " .. .
March 14, 2020

## 250

```const int N = 200 + 9;
int f[2][N][N], (*f0)[N], (*f1)[N];

class BearCries {
public:
int count(string message) {

int n = SZ(message); f0 = f[0], f1 = f[1];
REP(i, n) REP(j, n) f1[i][j] = 0; f1[0][0] = 1;

REP(i, n) {
char c = message[i];
swap(f0, f1); REP(i, n) REP(j, n) f1[i][j] = 0;
#define u f0[i][j]
REP(i, n) REP(j, n) if (u){
if (c == ';') {
f1[i+1][j] += u;
if (j) f1[i][j-1] += u*j;
} else {
if (i) f1[i-1][j+1] += u*i;
f1[i][j] += u*j;
}
}
}

return f1[0][0];
}
};
```

## 500

… 形式有点像叉积，感觉可以极角排序。

## 900

```const int N = 14;
typedef pair<Int,Int> pii;
pii f[2][1<<N], *f0, *f1, u;
// ways, score
int s, i, j, W, H;

void put(pii& v, int t) {
v.fi += u.fi;
v.se += u.fi*t + u.se;
}

void skip() {
put(f1[s&~_1(i+1)], 0);
}

bool putRight() {
if (j == W-1 || _1(s, i) || _1(s, i+1)) return 0;
put(f1[s|_1(i)], 1);
return 1;
}

bool putDown() {
if (i == H-1 || _1(s, i+1)) return 0;
put(f1[s|_1(i+1)], 1);
return 1;
}

class BearDestroys {
public:
int sumUp(int W, int H, int MOD) {
::MOD = MOD; ::W = W; ::H = H; f0 = f[0], f1 = f[1]; int S = 1<<H+1;
REP(s, S) f1[s] = {0,0}; f1[0] = {1,0};

REP(ij, W+H-1) {
int il = max(0, ij-W+1), ir = min(H, ij+1);
FOR_N(i, il, ir) {
j = ij - i; swap(f0, f1); REP(s, S) f1[s] = {0, 0};
REP_N(s, S) {
u = f0[s];
if (!putRight() && !putDown()) skip();
if (!putDown() && !putRight()) skip();
}
}
swap(f0, f1); REP(s, S) f1[s] = {0, 0};
REP(s, 1<<H) f1[s<<1] = f0[s];
}
//exit(0);

return f1[0].se;
}
};
```