# 某岛

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

## 250

（平局算负）

```class BeatTheStar {
public:
double doesItMatter(int n, int g) {
int s = n*(n+1)/2;
RST(dp); dp[0] = 1;
REP_1(i, n) if (i != g) {
DWN_1(j, s-i, 0) {
dp[j+i] += dp[j] * 0.5;
dp[j] = dp[j] * 0.5;
}
}
DB z = 0;
FOR_1(i, s/2-g+1, s/2) z += dp[i];
return z;
}
};
```

## 500

RMQ + 单调栈。。

```const int MOD = 1000000007;
const int INF = 0x7fffffff;
inline int clz(int x){return __builtin_clz(x);}
inline int lg2(int x){return !x ? -1 : 31 - clz(x);}

const int N = int(1e6)+9, LV = 21;
int h[N], l[N], r[N], sta[N], top;
int n;

int ST[LV][N];

int rmq(int l, int r){
int lv = lg2(r-l);
return min(ST[lv][l], ST[lv][r-(1<<lv)]);
}

class Prominence {
public:
long long sumOfProminences(int n, vector <int> coef, vector <int> idx, vector <int> val) {
h[0] = h[n+3] = INF; h[1] = h[n+2] = 0; REP(i, n) {
int p = i&1; LL a = coef[3*p], b = coef[3*p+1], c = coef[3*p+2];
h[i+2] = (((a*i+b)%MOD)*i+c)%MOD;
}
REP(i, SZ(idx)) h[idx[i]+2] = val[i]; n += 2;

sta[top = 0] = 0; REP_1(i, n) {
while (h[sta[top]] <= h[i]) --top;
l[i] = sta[top]; sta[++top] = i;
}
sta[top = 0] = n+1; DWN_1(i, n, 1) {
while (h[sta[top]] <= h[i]) --top;
r[i] = sta[top]; sta[++top] = i;
}

REP_1(i, n) ST[0][i] = h[i];
for ( int lv = 1 ; (1 << lv) <= n ; lv ++ ){
for ( int i = 1; i + (1 << lv)  <= n + 1 ; i ++ ){
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))]);
}
}

long long z = 0;
REP_1(i, n) if (h[i-1] < h[i] && h[i] > h[i+1]) {
z += h[i] - max(rmq(l[i]+1, i), rmq(i+1, r[i]));
}
return z;
}
};
```

1000

```const int N = 1009;
Int f[8][N], fp[8]; bool fb[N];
int n;

class RestrictedLeaves {
public:
int count(vector <int> parent) {

n = SZ(parent); REP(i, n) fb[i] = 1;

DWN(u, n, 1) {

if (fb[u]) { // leaf
f[0][u] = 1;
f[7][u] = 1;
}

int p = parent[u];

if (fb[p]) {
fb[p] = 0; REP(sp, 8) f[sp][p] = 0;
REP(su, 8) {
REP(sp, 2) {
int ss = su&3; if (sp) {
if (su&4) continue;
ss |= 4;
}
f[ss][p] += f[su][u];
}
}
} else {
REP(sp, 8) fp[sp] = f[sp][p], f[sp][p] = 0;
REP(su, 8) {
REP(sp, 8) {
if (sp&su&4) continue;
if ((sp&2)&&(su&1)) continue;
int ss = (su&2)|(sp&5);
f[ss][p] += f[su][u] * fp[sp];
}
}
}
}

Int z = 0; REP(s, 8) if((s&3)^3) z += f[s][0];
return z;
}
};
```